fork(1) download 
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. void PrintVector( const vector<int> & arr )
  8. {
  9. 	for( unsigned int i = 0; i < arr.size(); ++ i )
  10. 	{
  11. 		cout << arr[i] << ", ";
  12. 	}
  13. 	cout << endl;
  14. }
  15.  
  16. void ReadArray( vector<int> & arr )
  17. {
  18. 	ifstream arrfile("IntegerArray.txt");
  19. 	int a;
  20. 	while( arrfile >> a )
  21. 	{
  22. 		arr.push_back( a );
  23. 	}
  24. }
  25.  
  26. unsigned long int DumbInversions( const vector<int> & arr )
  27. {
  28. 	unsigned long int result = 0;
  29. 	for( unsigned int i = 0; i < arr.size() - 1; ++ i )
  30. 	{
  31. 		for( unsigned int j = i + 1; j < arr.size(); ++ j )
  32. 		{
  33. 			if( arr[i] > arr[j] )
  34. 				result ++;
  35. 		}
  36. 	}
  37. 	return result;
  38. }
  39.  
  40. unsigned long MergeSortInversions(
  41. 	const vector<int> & in,
  42. 	int from, int to,
  43. 	vector<int> & out
  44. 	)
  45. {
  46. 	int diff = to - from;
  47. 	if( diff == 0 )
  48. 	{
  49. 		out.push_back( in[from] );
  50. 		return 0;
  51. 	}
  52. 	if( diff == 1 )
  53. 	{
  54. 		if( in[from] < in[to] )
  55. 		{
  56. 			out.push_back( in[from] );
  57. 			out.push_back( in[to] );
  58. 			return 0;
  59. 		}
  60. 		else
  61. 		{
  62. 			out.push_back( in[to] );
  63. 			out.push_back( in[from] );
  64. 			return 1;
  65. 		}
  66. 	}
  67.  
  68. 	int div = (from + to) / 2;
  69. 	vector<int> arr_left;
  70. 	unsigned long inv_left = MergeSortInversions( in, from, div, arr_left );
  71. 	vector<int> arr_right;
  72. 	unsigned long inv_right = MergeSortInversions( in, div+1, to, arr_right );
  73. 	unsigned int r = 0;
  74. 	unsigned int l = 0;
  75. 	unsigned long invs = 0;
  76. 	for( int i = 0; i <= diff; ++ i )
  77. 	{
  78. 		if( l >= arr_left.size())
  79. 		{
  80. 			out.push_back( arr_right[r] );
  81. 			r ++;
  82. 			continue;
  83. 		}
  84. 		if( r >= arr_right.size())
  85. 		{
  86. 			out.push_back( arr_left[l] );
  87. 			l ++;
  88. 			continue;
  89. 		}
  90. 		if( arr_left[l] < arr_right[r])
  91. 		{
  92. 			out.push_back( arr_left[l] );
  93. 			l ++;
  94. 		}
  95. 		else
  96. 		{
  97. 			out.push_back( arr_right[r] );
  98. 			r ++;
  99. 			invs += arr_left.size() - l;
  100. 		}
  101. 	}
  102. 	return inv_left + inv_right + invs;
  103. }
  104.  
  105. unsigned long MergeSortInversions( const vector<int> & arr )
  106. {
  107. 	vector<int> sorted;	
  108. 	unsigned long int invs = MergeSortInversions( arr, 0, arr.size()-1, sorted);
  109. 	return invs;
  110. }
  111.  
  112. int main( /*int argc, char * argv[]*/ )
  113. {
  114. 	vector<int> arr;
  115. 	ReadArray( arr );
  116. 	unsigned long int good_result = 2407905288;
  117. 	cout <<  good_result << endl;
  118. 	cout << "Array of " << arr.size() << " elements." << endl;
  119. 	//unsigned long int dumb_inv = DumbInversions( arr );
  120. 	//cout << "Dumb inv: " << dumb_inv << endl;
  121. 	unsigned long int merge_inv = MergeSortInversions( arr );
  122. 	cout << "Merge inv: " << merge_inv << endl;
  123. 	return 0;
  124. }
  125.  
Runtime error #stdin #stdout 0s 3476KB
comments (?)
stdin 
Standard input is empty
stdout 
2407905288
Array of 0 elements.
https://ideone.com/680JfB
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!