Cod sursa(job #208862)

Utilizator mordredSimionescu Andrei mordred Data 19 septembrie 2008 12:56:41
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <fstream.h>
#define nmax 1000005
#define nrmax 2100000

int n,sir[nmax];
int xorr[nmax],trie[nmax],left[nrmax],right[nmax];
int sol,soli,solj,aux;

void insert(int long x,int long poz){
 int j,key=1;
 for(j=21;j>=0;j--)
    if( x & (1<<j) ){
       if(right[key]<0)
	       right[key]=++aux;
	   key=right[key];
	   }
	else{
       if(left[key]<0)
	       left[key]=++aux;
	   key=left[key];
	   }
 trie[key]=poz;
 }

void init(){
 int i;
 xorr[1]=sir[1];
 
 for(i=2;i<=n;i++)
    xorr[i]=xorr[i-1]^sir[i];
 
 sol=xorr[1], soli=1, solj=1, aux=1;
 
 memset(left,-1,sizeof(left));
 memset(right,-1,sizeof(right));
 
 insert(xorr[1],1);
}

int search(int long x){
 int key=1,j;
 for(j=21;j>=0;j--)
    if(x&1<<j)
	   if(right[key]>0)
	       key=right[key];
	   else
	       key=left[key];
    else
	   if(left[key]>0)
	       key=left[key];
	   else
	       key=right[key];
 return trie[key];
}

int solve(){
 int i,d;
 init();
 for(i=2;i<=n;i++){
   d=search(~xorr[i]);
   if(sol<(xorr[d]^xorr[i])){
        sol=xorr[d]^xorr[i];
	    soli=d+1;
	    solj=i;
	    }
   if(sol<xorr[i]){
     sol=xorr[i];
	 soli=1;
	 solj=i;
	 }
   insert(xorr[i],i);
   }
 return 0;
}

int main(){
 freopen("xormax.in","r",stdin);
 freopen("xormax.out","w",stdout);
 
 int i;
 scanf("%ld",&n);
 for(i=1;i<=n;i++)
    scanf("%ld",&sir[i]);
 
 solve();
 
 printf("%ld %ld %ld",sol,soli,solj);
 
 return 0;
 }