I have a nlogn solution for this problem, but I am getting a WA and I am unable to find out where I am going wrong.
Any hints??
Code is as follows:
#include<stdio.h>
int initpos[300000];
int moves[300000];
int n, complexity;
int temp1[300000], temp2[300000], temp;
void display() {
int j;
for ( j=0 ; j<n ; j++ ) printf("%d “,initpos[j]);
printf(”\n");
}
void merge ( int a, int b ) {
int mid;
int i, j;
int k, len1, len2;
if ( a==b ) return; //single element only
else {
mid = (a+b)>>1;
merge(a, mid);
merge(mid + 1, b);
k = mid + 1; len1 = mid - a + 1; j = 0; temp = a; len2 = b - mid;
while (len1>0 || len2>0) {
//printf("loop run\n");
if (!len2 || (moves[k] - len1) < 0 ){ temp1[j] = initpos[temp]; temp2[j++] = moves[temp++]; len1--; }
else { temp1[j] = initpos[k]; temp2[j++] = moves[k++]-len1; len2--; }
complexity++;
}
//replace the merged data
for (k=a, j=0 ; k<=b; k++, j++) { initpos[k] = temp1[j]; moves[k] = temp2[j];}
}
}
int main () {
int t = 0;
int i;
int j, k;
int shift;
scanf("%d",&t);
for ( i=0 ; i<t; i++ ) {
scanf("%d",&n);
for ( j=0 ; j<n ; j++ ) {
scanf("%d", &moves[j]);
initpos[j] = j+1;
}
complexity = 0;
merge (0, n-1);
display();
}
return 0;
}