URI PROBLEMA 1088 - Bolhas e Baldes SOLUÇÃO EM C++

URI Online Judge | 1088

Bolhas e Baldes

Por Cláudio L. Lucchesi  Brasil

Timelimit: 3

Andrea, Carlos e Marcelo são muito amigos e passam todos os finais de semana à beira da piscina. Enquanto Andrea se bronzeia ao sol, os dois ficam jogando Bolhas. Andrea, uma cientista da computação muito esperta, já disse a eles que não entende por que passam tanto tempo jogando um jogo tão primário.

Usando o computador portátil dela, os dois geram um inteiro aleatório N e uma seqüência de inteiros, também aleatória, que é uma permutação de 1, 2, . . . ,N.

O jogo então começa, cada jogador faz um movimento, e a jogada passa para o outro jogador. Marcelo é sempre o primeiro a começar a jogar. Um movimento de um jogador consiste na escolha de um par de elementos consecutivos da seqüência que estejam fora de ordem e em inverter a ordem dos dois elementos. Por exemplo, dada a seqüência 1, 5, 3, 4, 2, o jogador pode inverter as posições de 5 e 3 ou de 4 e 2, mas não pode inverter as posições de 3 e 4, nem de 5 e 2. Continuando com o exemplo, se o jogador decide inverter as posições de 5 e 3 então a nova seqüência será 1, 3, 5, 4, 2.

Mais cedo ou mais tarde, a seqüência ficará ordenada. Perde o jogador impossibilitado de fazer um movimento. Andrea, com algum desdém, sempre diz que seria mais simples jogar cara ou coroa, com o mesmo efeito. Sua missão, caso decida aceitá-la, é determinar quem ganha o jogo, dada a seqüência inicial.

Entrada

A entrada contém vários casos de teste. Os dados de cada caso de teste estão numa única linha, e são inteiros separados por um espaço em branco. Cada linha contém um inteiroN (2 ≤ N ≤ 10⁵), seguido da seqüência inicial P = (X₁, X₂, ...,X_N) de N inteiros distintos dois a dois, onde1 ≤ X_i ≤ N para 1 ≤ i ≤ N.

O final da entrada é indicado por uma linha que contém apenas o número zero.

Saída

Para cada caso de teste da entrada seu programa deve imprimir uma única linha, com o nome do vencedor, igual a Carlos ou Marcelo., sem espaços em branco.

#include <cstdio>
#include <cstring>
#include <vector>

#define PB push_back
#define SC1(a) scanf("%d", &a)
#define FOR(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef vector<int> vi;

vi v;
int counter = 0;

vi merge(vi a, vi b)
{
    int i = 0, j = 0, s1 = a.size(), s2 = b.size();
    vi r;
   
    while(i  < s1 && j < s2)
    {
        if(a[i] < b[j]){
            r.PB(a[i]);
            i++;
        }else{
            r.PB(b[j]);
            counter += (int)(a.size()) - i;
            j++;
        }
    }
   
    while( i < s1)
    {
        r.PB(a[i]);
        i++;
    }

    while(j < s2)
    {
        r.PB(b[j]);
        j++;
    }

    return r;
}

vi mergeSort(int left, int right)
{
    vi r;
    int middle = (left + right)/2;
   
    if(left + 1 >= right){
        r.PB(v[left]);
        return r;
    }
   
    vi a = mergeSort(left, middle);
    vi b = mergeSort(middle, right);
    r = merge(a,b);
   
    return r;
}

int main (int argc, char *argv[])
{
    int n, x;
   
    while(SC1(n) && n)
    {
        counter = 0;
        v.clear();
       
        FOR(i, n)
        {
            SC1(x);
            v.PB(x);
        }
       
        mergeSort(0,n);
       
        if(counter % 2) puts("Marcelo");
        else puts("Carlos");
    }
   
    return 0;
}