Cod sursa(job #24789)

Utilizator pocaituDavid si Goliat pocaitu Data 3 martie 2007 16:46:25
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<stdio.h>
#include<fstream.h>

#define fin "xormax.in"
#define fout "xormax.out"
#define nil -1
#define nmax 100005
#define nrmax 2100000

int long n,xorr[nmax],trie[nrmax],lung,fst[nrmax],fdr[nrmax],sol,inc,sf,sir[nmax];

void insert(int long x,int long poz)
{int long j,key=1;
 for(j=20;j>=0;j--)
	if(x&(1<<j))
	   {if(fdr[key]<0)
			fdr[key]=++lung;
		 key=fdr[key];
		}
	 else
	   {if(fst[key]<0)
			fst[key]=++lung;
		 key=fst[key];
		}

 trie[key]=poz;

 }
void init()
{int long i;
  xorr[1]=sir[1];
 for(i=2;i<=n;i++)
  xorr[i]=xorr[i-1]^sir[i];
 sol=xorr[1];
 inc=1; sf=1;
 lung=1;
 memset(fst,nil,sizeof(fst));
 memset(fdr,nil,sizeof(fdr));
 insert(xorr[1],1);
}





int long search(int long x)//cauta trie[k] cel mai apropiat de x
{int long key=1,j;
 for(j=20;j>=0;j--)
  if(x&1<<j)
	if(fdr[key]>0)
	  key=fdr[key];
	else
	  key=fst[key];
  else
	if(fst[key]>0)
	 key=fst[key];
	else
	 key=fdr[key];


 return trie[key];

 }





int long rezolva()
{int long i,d;
 init();
 for(i=2;i<=n;i++)
  {d=search(~xorr[i]);
   if((xorr[d]^xorr[i])<sol)
	 {sol=xorr[d]^xorr[i];
	  inc=d+1;
	  sf=i;
	  }
   if(sol<xorr[i])
	 {sol=xorr[i];
	  inc=1;
	  sf=i;
	  }

   insert(xorr[i],i);
   }
 return 0;
 }



void afiseaza()
{freopen(fout,"w",stdout);
 printf("%ld %ld %ld",sol,inc,sf);
 fclose(stdout);
 }

void citire()
{int long i;
 freopen(fin,"r",stdin);
 scanf("%ld",&n);
 for(i=1;i<=n;i++)
  scanf("%ld",&sir[i]);
}




int main()
{citire();
 rezolva();
 afiseaza();
 return 0;
 }