Cod sursa(job #196821)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 29 iunie 2008 13:34:29
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
const int NMAX=100001,b=21;
typedef struct trie{
        trie *leg[2];
        int poz;
        };
int x[NMAX],a,n,ls,ld,max=-1,s,d,rez,i,j;
trie *t;
trie *creare(){
     trie *p=new trie;
     p->leg[0]=NULL;
     p->leg[1]=NULL;
     p->poz=0;
     return p;
     }
void add(trie *t,int w,int p){
     int k;
     if (p==0) t->poz=i;
     else {
       if ((1<<p)&w) k=1;
                else k=0;   
       if (!t->leg[k]) t->leg[k]=creare();
       add(t->leg[k],w,p-1);
       }
     }
int find(trie *t,int w,int p){
    int k;
    if (p==0) return t->poz;
    else {
      if ((1<<p)&w) k=0;
               else k=1;
      if (!t->leg[k]) k=1-k;
      return find(t->leg[k],w,p-1);
      }
    }            
void search(){
     d=i;
     s=find(t,x[i],b);
     rez=x[s]^x[d];
     s++;
     }
int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    t=creare();
    i=0;add(t,0,b);
    for (i=1;i<=n;++i){
         scanf("%d",&a);
         x[i]=x[i-1]^a;
         add(t,x[i],b);
         search();
         if (rez>=max) max=rez,ls=s,ld=d;
         }
    printf("%d %d %d",max,ls,ld);
    return 0;
}