Cod sursa(job #143565)

Utilizator damaDamaschin Mihai dama Data 26 februarie 2008 17:47:30
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>

int n, s[100001], x[1000000], sol = -1, start, end, counter, newsol;
int trie[2][1000000], cnt;

void adauga(int, int, int);
void cauta(int, int, int);

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    int a, i, j;

    scanf("%d", &n);

    for(i = 1; i <= n; ++i)
    {
        scanf("%d", &a);
        s[i] = s[i - 1] ^ a;
        //printf("%d %d %d\n", i, s[i], v[i]);
    }
    adauga(20, 0, 0);
    for(counter = 1; counter <= n; ++counter)
    {
        newsol = 0;
        cauta(20, 0, s[counter]);
        adauga(20, 0, s[counter]);
    }

    printf("%d %d %d\n", sol, start, end);

    return 0;
}

void cauta(int depth, int nod, int val)
{
    if(depth == -1)
    {
        if(newsol > sol)
        {
            sol = newsol;
            start = x[nod] + 1;
            end = counter;
        }
        return;
    }
    if(val & (1 << depth))
    {
        if(trie[0][nod])
        {
            newsol += 1 << depth;
            cauta(depth - 1, trie[0][nod], val);
        }
        else
        {
            cauta(depth - 1, trie[1][nod], val);
        }
    }
    else
    {
        if(trie[1][nod])
        {
            newsol += 1 << depth;
            cauta(depth - 1, trie[1][nod], val);
        }
        else
        {
            cauta(depth - 1, trie[0][nod], val);
        }
    }
}

void adauga(int depth, int nod, int val)
{
    if(depth == -1)
    {
        x[nod] = counter;
        return;
    }
    if(val & (1 << depth))
    {
        if(!trie[1][nod])
        {
            trie[1][nod] = ++cnt;
        }
        adauga(depth - 1, trie[1][nod], val);
    }
    else
    {
        if(!trie[0][nod])
        {
            trie[0][nod] = ++cnt;
        }
        adauga(depth - 1, trie[0][nod], val);
    }
}