11495 - Bubbles and Buckets

Again a very simple problem, just count the no of inversions in each game instance if it's even second guy wins if it's odd the guy who starts the game (i.e. the first guy) wins.

//
//  main.cpp
//  11495 - Bubbles and Buckets
//
//  Created by Panks on 06/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstdlib>


unsigned long long int mergeSort(long long int arr[], long long int array_size);
unsigned long long int  _mergeSort(long long int arr[], long long int temp[], long long int left, long long int right);
unsigned long long int merge(long long int arr[], long long int temp[], long long int left, long long int mid, long long int right);

using namespace std;
int main (int argc, const char * argv[])
{
    long long int t,count, tmp;
    unsigned long long inv;
    long long int store[100000+1];
    while (scanf("%lld", &t)&&t) {
        count=0;
        tmp=t;
        while (t--) {
            scanf("%lld", &store[count]);
            count++;
        }
        inv=mergeSort(&store[0], tmp);
        if (inv%2==0) {
            cout<<"Carlos\n";
        }else{
            cout<<"Marcelo\n";
        }        
    }

    return 0;
}


unsigned long long mergeSort(long long int arr[], long long int array_size)
{
    long long int *temp = (long long int *)malloc(sizeof(long long int)*array_size);
    return _mergeSort(arr, temp, 0, array_size - 1);
}


unsigned long long _mergeSort(long long int arr[], long long int temp[], long long int left, long long int right)
{
    long long int mid;
    unsigned long long inv_count = 0;
    if (right > left)
    {

        mid = (right + left)/2;

        inv_count  = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid+1, right);
        
        inv_count += merge(arr, temp, left, mid+1, right);
    }
    return inv_count;
}

unsigned long long int merge(long long int arr[], long long int temp[], long long int left, long long int mid, long long int right)
{
    long long int i, j, k;
    unsigned long long int inv_count = 0;
    
    i = left; /* i is index for left subarray*/
    j = mid;  /* i is index for right subarray*/
    k = left; /* i is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right))
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
            
            inv_count = inv_count + (mid - i);
        }
    }
    
    while (i <= mid - 1)
        temp[k++] = arr[i++];
    
    while (j <= right)
        temp[k++] = arr[j++];
    
    for (i=left; i <= right; i++)
        arr[i] = temp[i];
    
    return inv_count;
}