Cod sursa(job #24781)

Utilizator pocaituDavid si Goliat pocaitu Data 3 martie 2007 16:37:43
Problema Xor Max Scor 0
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,xor[nmax],trie[nrmax],lung,f_st[nrmax],f_dr[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(f_dr[key]<0)
			f_dr[key]=++lung;
		 key=f_dr[key];
		}
	 else
	   {if(f_st[key]<0)
			f_st[key]=++lung;
		 key=f_st[key];
		}

 trie[key]=poz;

 }
void init()
{int long i;
  xor[1]=sir[1];
 for(i=2;i<=n;i++)
  xor[i]=xor[i-1]^sir[i];
 sol=xor[1];
 inc=1; sf=1;
 lung=1;
 memset(f_st,nil,sizeof(f_st));
 memset(f_dr,nil,sizeof(f_dr));
 insert(xor[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(f_dr[key]>0)
	  key=f_dr[key];
	else
	  key=f_st[key];
  else
	if(f_st[key]>0)
	 key=f_st[key];
	else
	 key=f_dr[key];


 return trie[key];

 }





int long rezolva()
{int long i,d;
 init();
 for(i=2;i<=n;i++)
  {if(sol<=xor[i])
	 {sol=xor[i];
	  inc=1;
	  sf=i;
	  }
   d=search(~xor[i]);
   if(xor[d]^xor[i]<=sol)
	 {sol=xor[d]^xor[i];
	  inc=d+1;
	  sf=i;
	  }
   insert(xor[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;
 }