s4553711
5/4/2014 - 5:03 PM

## UVA-10810

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// The source of this code is http://kasonblog.blogspot.tw/2012/04/10810-ultra-quicksort-uva-online-judge.html
// and its realted information http://program-lover.blogspot.tw/2008/10/mergesort.html
// or http://programming-study-notes.blogspot.tw/2013/12/uva-10810-ultra-quicksort.html
// or http://www.tuicool.com/articles/ANb6Fv

long long ans;
int a1[500100], a2[500100];

void merge_sort(int a, int b) {
int tmp, mid, t1, t2;

if (a+1 == b){
return;
}

mid = (a+b)/2;

merge_sort(a,mid);
merge_sort(mid,b);

printf("Log> Perform .. %d -> %d\n",a,b);

t1 = a;
t2 = mid;

printf("log> t%d -> t%d\n",t1,t2);

tmp = a;
while(t1<mid && t2<b){
if(a1[t1] < a1[t2]){
printf("m1  a2[%d] < a1[%d] ( %d <- %d)\n",tmp,t1,a2[tmp],a1[t1]);
a2[tmp++]= a1[t1++];
} else {
printf("m2  a2[%d] < a1[%d] ( %d <- %d)\n",tmp,t2,a2[tmp],a1[t2]);
a2[tmp++] = a1[t2++];
ans += mid - t1;
}
}

while(t1<mid){
printf("31> %d, %d\n",t1,mid);
a2[tmp++] = a1[t1++];
}
while(t2<b){
printf("32> %d, %d\n",t2,b);
a2[tmp++] = a1[t2++];
}

memcpy(&a1[a], &a2[a], (b-a)*sizeof(int));
}

int main() {
int n, i;

while(scanf("%d", &n) != EOF){
if(n == 0)
return 0;
for(i=0; i<n; i++)
scanf("%d", &a1[i]);
ans = 0;
merge_sort(0, n);
printf("%lld\n", ans);
}

return 0;
}``````