fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4.  
  5. int merge(int arr[], int temp[], int left, int mid, int right)
  6. {
  7.     int inv_count = 0;
  8.  
  9.     int i = left; /* i is index for left subarray*/
  10.     int j = mid;  /* j is index for right subarray*/
  11.     int k = left; /* k is index for resultant merged subarray*/
  12.     while ((i <= mid - 1) && (j <= right))
  13.     {
  14.         if (arr[i] <= arr[j])
  15.             temp[k++] = arr[i++];
  16.         else
  17.         {
  18.             temp[k++] = arr[j++];
  19.  
  20.             /* this is tricky -- see above explanation/
  21.               diagram for merge()*/
  22.             inv_count = inv_count + (mid - i);
  23.         }
  24.     }
  25.  
  26.     /* Copy the remaining elements of left subarray
  27.      (if there are any) to temp*/
  28.     while (i <= mid - 1)
  29.         temp[k++] = arr[i++];
  30.  
  31.     /* Copy the remaining elements of right subarray
  32.      (if there are any) to temp*/
  33.     while (j <= right)
  34.         temp[k++] = arr[j++];
  35.  
  36.     /*Copy back the merged elements to original array*/
  37.     for (i=left; i <= right; i++)
  38.         arr[i] = temp[i];
  39.  
  40.     return inv_count;
  41. }
  42.  
  43. /* An auxiliary recursive function that sorts the input
  44.    array and returns the number of inversions in the
  45.    array. */
  46. int _mergeSort(int arr[], int temp[], int left, int right)
  47. {
  48.     int mid, inv_count = 0;
  49.     if (right > left)
  50.     {
  51.         /* Divide the array into two parts and call
  52.           _mergeSortAndCountInv() for each of the parts */
  53.         mid = (right + left)/2;
  54.  
  55.         /* Inversion count will be sum of inversions in
  56.            left-part, right-part and number of inversions
  57.            in merging */
  58.         inv_count  = _mergeSort(arr, temp, left, mid);
  59.         inv_count += _mergeSort(arr, temp, mid+1, right);
  60.  
  61.         /*Merge the two parts*/
  62.         inv_count += merge(arr, temp, left, mid+1, right);
  63.     }
  64.  
  65.     return inv_count;
  66. }
  67.  
  68. int getMinNumMoves(vector<ll> v)
  69. {
  70. 	int n = v.size();
  71. 	int a[n];
  72. 	for(ll i=0;i<n;i++)
  73. 	{
  74. 		a[i]=v[i];
  75. 	}
  76. 	 int temp[n];
  77. 	 return _mergeSort(a, temp, 0, n - 1);
  78. }
  79.  
  80. int main() {
  81. 	// your code goes here
  82. 	ll n;
  83. 	cin>>n;
  84. 	vector<ll> v(n);
  85. 	for(ll i=0;i<n;i++)
  86. 	{
  87. 		cin>>v[i];
  88. 	}
  89. 	cout<<getMinNumMoves(v);
  90. 	return 0;
  91. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
5
2 4 3  1 6
stdout
copy 
4
https://ideone.com/KGfA23
language:
C++14 (gcc 8.3)
created:
12 days 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!