Cod sursa(job #1016268)

Utilizator nicuvladNicu Vlad nicuvlad Data 25 octombrie 2013 23:14:23
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstdio>
#define NMAX 100000+5
using namespace std;
struct trie
{
    int poz;
    trie *urm[2];
    trie()
    {
        poz=0;
        urm[0]=urm[1]=0;
    }
};
trie *root;
int N,X[NMAX];
void add(int x,int p)
{
    int i,j;
    trie *nod=root;
    for(i=20;i>=0;i--)
    {
        j=(1<<i)&x;
        if(j) j=1;
        if(nod->urm[j]==NULL) nod->urm[j]=new trie;
        nod=nod->urm[j];
    }
    nod->poz=p;
}
int search(int x)
{
    int i,j;
    trie *nod=root;
    for(i=20;i>=0;i--)
    {
        j=(1<<i)&x;
        if(j) j=1;
        if(nod->urm[!j]) nod=nod->urm[!j];
        else nod=nod->urm[j];
    }
    return nod->poz;
}
int main()
{
    int i,a,sol,st,dr;
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&N);
    sol=-1;
    root=new trie;
    add(0,0);
    for(i=1;i<=N;i++)
    {
        scanf("%d",&a);
        X[i]=X[i-1]^a;
        a=search(X[i]);
        if((X[a]^X[i])>sol) sol=X[a]^X[i],st=a+1,dr=i;
        add(X[i],i);
    }
    printf("%d %d %d\n",sol,st,dr);
    return 0;
}