範例程式碼 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;
}