範例程式碼 uva11495
//uva11495
#include <iostream>
using namespace std;
long long merge(int *P, int left, int mid, int right){
int *tmp = new int[right - left + 1];
long long sum = 0;
int iLeft = left;
int iRight = mid+1;
int iMerge = 0;
// the middle reverse numbers
while(iLeft <= mid && iRight <= right){
if(P[iLeft] <= P[iRight]){
tmp[iMerge++] = P[iLeft++];
}else{
tmp[iMerge++] = P[iRight++];
sum += mid - iLeft + 1; // key point
}
}
while(iLeft <= mid)
tmp[iMerge++] = P[iLeft++];
while(iRight <= right)
tmp[iMerge++] = P[iRight++];
for(int i = left ; i <= right ; ++i)
P[i] = tmp[i - left];
delete [] tmp;
return sum;
}
long long mergesort(int *P, int left, int right){
long long sum=0;
// reverse number = left reverse numbers + right reverse numbers + the middle reverse numbers
if(left < right){
int mid = (left + right) / 2;
sum = mergesort(P, left, mid);
sum += mergesort(P, mid+1, right);
sum += merge(P, left, mid, right);
}
return sum;
}
int main(){
int n;
while(cin >> n && n){
int *P = new int[n];
for(int i=0 ; i < n ; ++i) // read in permutation
cin >> P[i];
long long ans = mergesort(P,0,n-1); // count the reverse order number
if(ans % 2 == 0)
cout << "Carlos " << ans << endl;
else
cout << "Marcelo " << ans << endl;
delete [] P;
}
return 0;
}