I tried to solve this problem using merge sort logic, the algorithm is same as merge sort, only change is in the merge step where i am counting the inversion_count. I tested some test cases and I am getting correct answer, but I am getting WA on spoj. Is the code incorrect or any test case whr it fails?
http://www.spoj.pl/problems/INVCNT/ #include<iostream> using namespace std; long inversion_count = 0; void merge(long arr[], long p, long q, long r) { long n1 = q-p+1; long n2 = r-q; long L[n1]; long R[n2]; for(long i=0;i<n1;i++) { L[i]=arr[p+i]; } L[n1]=99999999; for(long i=0;i<n2;i++) { R[i]=arr[q+1+i]; } R[n2]=9999999; long i=0; long j=0; long k=p; while(k<=r) { if(L[i]<=R[j]) { arr[k]=L[i]; i++; k++; } else if(L[i]>R[j]) { arr[k]=R[j]; j++; k++; inversion_count+=n1-i; } } } void merge_sort(long arr[], long p, long r) { if(p<r) { long q = (p+r)/2; merge_sort(arr,p,q); merge_sort(arr,q+1,r); merge(arr,p,q,r); } } int main() { int t; char a; long n,i; long arr[200002]; scanf("%d",&t); while(t--) { scanf("%ld",&n); for(i=0;i<n;i++) scanf("%ld",&arr[i]); merge_sort(arr,0,n-1); cout<<inversion_count<<"\n"; inversion_count=0; } return 0; } -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
