Cod sursa(job #581283)

Utilizator drywaterLazar Vlad drywater Data 13 aprilie 2011 23:10:39
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
int n,b,i,val,x[100001],poz,a,max;
struct Trie{int poz; Trie *fiu[2];
Trie(){poz=-1; fiu[0]=fiu[1]=0;}};
Trie *t=new Trie;
int caut(Trie *nod,int val,int bit)
{
    int x;
    if (bit==-1) return nod->poz;
    x=!(((1<<bit)&val)>>bit);
    if (nod->fiu[x]) return caut(nod->fiu[x],val,bit-1);
    else {x=1-x; return caut(nod->fiu[x],val,bit-1);}

}
int ins(Trie *nod,int val,int bit)
{
    if (bit==-1)
    {
        nod->poz=i;
        return 0;
    }
    int x=((1<<bit)&val)>>bit;
    if (!nod->fiu[x]) nod->fiu[x]=new Trie;
    ins(nod->fiu[x],val,bit-1);
}
int main(void)
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    ins(t,0,24);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a);
        x[i]=x[i-1]^a;
        a=x[i];
        val=caut(t,x[i],24);
        poz=0;
        ins(t,x[i],24);
        if (i>1 && x[i]^x[val]>max)
        {
            max=x[i]^x[val];
            a=val+1;
            b=i;
        }
    }
    printf("%d %d %d\n",max,a,b);
    return 0;
}