Cod sursa(job #196825)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 29 iunie 2008 14:10:08
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
const int NMAX=100001,b=20;
typedef struct trie{
        trie *leg[2];
        int poz;
        };
int x[NMAX],n,ls,ld,max=-1,r,i,j;
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);
      }
    }   
trie *t=creare();         
int main(){
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    add(t,0,b);
    for (i=1;i<=n;++i){
         scanf("%d",&j);
         x[i]=x[i-1]^j;
         j=find(t,x[i],b);
         r=x[j]^x[i];
         if (r>max) max=r,ls=j+1,ld=i;
         add(t,x[i],b);
         }
    printf("%d %d %d",max,ls,ld);
    return 0;
}