Cod sursa(job #573728)

Utilizator MKLOLDragos Ristache MKLOL Data 6 aprilie 2011 15:36:12
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<algorithm>
#include<stdio.h>

struct trie
{
    trie *fiu[2];
    int poz;

    trie()
    {
        fiu[0]=fiu[1]=0;
        poz=0;
    }
}*T=new trie;
int N,ind,sum,x,P,maxim,indf,inds;
void insert(trie* nod,int lvl,int val,int poz)
{//printf("%d ",lvl);
    if(!lvl)
    {
        nod->poz=poz;
        return;
    }


    --lvl;
    if(nod->fiu[(val&(1<<lvl))>>lvl]==NULL)
        nod->fiu[(val&(1<<lvl))>>lvl]=new trie;
    insert(nod->fiu[(val&(1<<lvl))>>lvl],lvl,val,poz);
}
int search(trie* nod,int lvl,int val)
{
    if(!lvl)
    {
        ind=nod->poz;
        return 0;
    }
    --lvl;
    if (nod->fiu[1^((val&(1<<lvl))>>lvl)])
        return ((1^((val&(1<<lvl))>>lvl))<<lvl)+search(nod->fiu[1^((val&(1<<lvl))>>lvl)],lvl,val);
    return (val&(1<<lvl))+ search(nod->fiu[(val&(1<<lvl))>>lvl],lvl,val);
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&N);
   insert(T,22,0,0);
    sum=0;
    for(int i=1;i<=N;++i)
    {
        scanf("%d",&x);
        sum^=x;
        P=search(T,22,sum);
        if(P^sum>maxim)
        {
            maxim=P^sum;
            inds=ind+1;
            indf=i;
        }
        insert(T,22,sum,i);
    }
    printf("%d %d %d\n",maxim,inds,indf);

}