Cod sursa(job #692857)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 26 februarie 2012 20:12:59
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <algorithm>

#define lim 22
#define MAX 100050

using namespace std;

int v[MAX], maxim, start, end;

struct Trie
{
    int inf;
    Trie *st, *dr;
    Trie()
    {
        inf = 0;
        st = dr = 0;
    }
}*T = new Trie;

void add(Trie *nod, int poz, int x)
{
    int i, bit;
    for(i = lim; i >= 0; i--)
    {
        bit = (x & (1 << i));
        if(bit)
        {
            if(!nod->st)
                nod->st = new Trie;
            nod = nod->st;
        }
        else
        {
            if(!nod->dr)
                nod->dr = new Trie;
            nod = nod->dr;
        }
    }
    nod->inf = poz;
}

int lookAfter(Trie *nod, int x)
{
    int i, bit;
    for(i = lim; i >= 0; i--)
    {
        bit = (x & (1 << i));
        if(bit)
        {
            if(nod->dr)
                nod = nod->dr;
            else
                nod = nod->st;
        }
        else
        {
            if(nod->st)
                nod = nod->st;
            else
                nod = nod->dr;
        }
    }
    return nod->inf;
}

int main()
{
    int n, i, j;
    freopen("xormax.in", "r", stdin);
    scanf("%d", &n);
    add(T, 0, 0);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
        v[i] ^= v[i - 1];
        j = lookAfter(T, v[i]);
        if(v[j] ^ v[i] > maxim)
        {
            maxim = v[j] ^ v[i];
            start = j;
            end = i;
        }
        add(T, i, v[i]);
    }
    fclose(stdin);
    freopen("xormax.out", "w", stdout);
    printf("%d %d %d",maxim, start + 1, end);
    return 0;
}