Alpha Score (Divide & Conquer Challenge)

#1

Cant find why am I getting WA for just 1 case !

Here’s My Code :
#include
using namespace std;
#define ll long long int
#define inf (ll)(1e9+7)

ll merging(ll arr[],int l,int mid,int h)
{
int p1 = l,p2 = mid+1;
ll temp[h-l+1];
ll ans2 = 0;
int k = 0;

while(p1<=mid || p2<=h)
{
    if(p1>mid)
        temp[k++] = arr[p2++];
    
    else if(p2>h)
        temp[k++] = arr[p1++];
    
    else if(arr[p2] < arr[p1])
        temp[k++] = arr[p2++];
    
    else
    {
        ll t = (arr[p1]%inf * (h-p2+1)%inf)%inf;
        ans2 = (ans2%inf + t%inf)%inf;
        temp[k++] = arr[p1++];
    }
}

k = 0;
for(int i=l;i<=h;i++)
    arr[i] = temp[k++];

return (ans2)%inf;

}

ll ans(ll arr[],int l,int h)
{
if(l==h)
return 0;

int mid = (l+h)>>1;
ll left = ans(arr,l,mid);
ll right = ans(arr,mid+1,h);
ll merge = merging(arr,l,mid,h);

ll lr = (left%inf + right%inf)%inf;

ll ans1 = (lr%inf + merge%inf)%inf;
return (ans1)%inf;

}

int main() {
int n;
cin>>n;

ll arr[n];
for(int i=0;i<n;i++)
    cin>>arr[i];

cout<<(ans(arr,0,n-1)+inf)%inf<<endl;

}

#2

use merge sort inversion count method.
paste your code on coding blocks IDE and share the link here.
you are definitely missing some corner cases.

#3

Here’s the code link : https://ide.codingblocks.com/s/57450

PS: I have used merge sort inversion count method.Still WA for 1 case.

#4

Check for Equal Values:
Test Case:
5
5 5 5 5 5

#5

Thanks.I found my mistake.AC! :smiley:

1 Like