Cod sursa(job #228522)

Utilizator Mishu91Andrei Misarca Mishu91 Data 7 decembrie 2008 14:05:50
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>

#define MAX_N 100006

typedef struct nod
{
    int poz;
    nod *fiu[2];

    nod()
    {
        poz = 0;
        fiu[0] = NULL;
        fiu[1] = NULL;
    }
} *Trie;

Trie T = new nod;
int N, V[MAX_N], Rez = -1, Pi, Ps;

void add(Trie &A, int nr, int p, int poz)
{
    if(p == -1)
    {
        A -> poz = poz;
        return;
    }

    int next = (((1 << p) & nr) >> p);
    if(A -> fiu[next] == NULL)
        A -> fiu[next] = new nod;
    add(A -> fiu[next], nr, p-1, poz);
}

int find(Trie A, int nr, int p)
{
    if(p == -1)
        return A -> poz;

    int next = (((1 << p) & nr) >> p);
    if(A -> fiu[1 - next])
        return find(A -> fiu[1 - next], nr, p - 1);
    return find(A -> fiu[next], nr, p - 1);
}

int main()
{
    freopen("xormax.in","rt",stdin);
    freopen("xormax.out","wt",stdout);

    scanf("%d",&N);
    int k;

    add(T, 0, 20, 0);

    for(int i = 1; i <= N; ++i)
    {
        scanf("%d",&k);
        V[i] = V[i-1] ^ k;
        int j = find(T, V[i], 20);
        if(V[i] ^ V[j] > Rez)
            Rez = V[i] ^ V[j], Pi = j+1, Ps = i;
        add(T, V[i], 20, i);
    }
    printf("%d %d %d",Rez, Pi, Ps);
}