Here is the link:-https://www.interviewstreet.com/challenges/dashboard/#problem/4e90477dbd22b I tried it using Merge sort,it passes 7/10 test cases but fails in rest of 3.Can anyone find bugs in my program. Thanks in advance.
#include<iostream>
#include<new>
using namespace std;
long int w =0;
void MERGE(long int*A,long int p,long int q,long int r)
{
long int x=q-p+1;
long int y=r-q;
long int*L=new long int [x];
long int*R=new long int [y];
for(long int i=0;i<x;i++)
L[i]=A[p+i];
for(long int i=0;i<y;i++)
R[i]=A[q+i+1];
long int i=0,j=0;
long int k;
for( k=p;i<x && j<y;k++)
{
if(L[i]<=R[j])
{A[k]=L[i];
i++;
}
else
{A[k]=R[j];
w += x-i;
j++;
}
}
if(i==x)
{
while(j<y)
{A[k]=R[j];
j++;
k++;
}
}
else if(j==y)
{
while(i<x)
{A[k]=L[i];
i++;
k++;
}
}
}
void MERGESORT(long int*A,long int p,long int r)
{if(p<r)
{long int q=(p+r)/2;
MERGESORT(A,p,q);
MERGESORT(A,q+1,r);
MERGE(A,p,q,r);
}
}
int main()
{
int T;
cin>>T;
for(int t=0;t<T;t++)
{ w =0;
long int n;
cin>>n;
long int a[n];
for(long int i=0;i<n;i++)
{
cin>>a[i];
}
MERGESORT(a,0,n-1);
/* for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;*/
cout<<w<<endl;
}
// system("pause");
return 0;
}
maybe overflow?
Thanks.can u give me a test case which fails my program?
try any case with answer greater than 2^31, e.g N = 105, a[i] = Const - i
long int
is usually equals toint
and equals to 32 bitYou have to use 64bit integer,
long long
slowpoke
its slowpoke..not >>slowpok<<