Cod sursa(job #371347)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 4 decembrie 2009 22:50:44
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#define FIN "xormax.in"
#define FOUT "xormax.out"
#define NMAX 100001
#define CHMAX 20
#define sh (*s-'0')
using namespace std;
int p,n,a[NMAX],b[NMAX],xr[NMAX],f,l,ind,w;

struct Trie
       {int index;
       Trie  *bin[2];
       Trie()
       {index=0;;memset(bin,0,sizeof(bin));}};
       Trie *t=new Trie();
void insert(Trie *nod,int b)
     {if(b==-1) {nod->index=p;return;}
     int vl=w&(1<<b);
     if(vl) vl=1;
     if(nod->bin[vl]==0) {nod->bin[vl]=new Trie();}
     insert(nod->bin[vl],b-1);}
int cauta(Trie *nod,int b)
     {if(b==-1) {return nod->index;}
      int vl=w&(1<<b);
      if(vl) vl=1;
      if(nod->bin[vl]==0)
       {if(vl==0) vl=1;
        else vl=0;
                       }
     if(nod->bin[vl]==0) return 0;
     return cauta(nod->bin[vl],b-1);                  
              }
int main()
{freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&n);
int r=0,x,k;
w=0;
p=0;
insert(t,CHMAX);
for(int i=1;i<=n;i++) {scanf("%d",&x);xr[i]=(x^xr[i-1]);
                         w=(~xr[i]);
                         k=cauta(t,CHMAX);
                         if(k) if(r< (xr[i]^xr[k])) {r=(xr[i]^xr[k]);f=k+1;l=i;}
                         w=xr[i];
                         p=i;
                         insert(t,CHMAX);
                         }
printf("%d %d %d",r,f,l);
    
    }