Cod sursa(job #330521)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 10 iulie 2009 13:46:13
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <cstring>

#define file_in "xormax.in"
#define file_out "xormax.out"

struct trie
{
	int poz,nrf;
	trie *a[20];
	
	trie()
	{
		poz=nrf=0;
		memset(a,0,sizeof(a));
	}
}*rad = new trie;


int inc,n,x,xx,sf,max,q,p;

void insert_tr(trie *nod, int lvl, int x, int ind)
{
	if (lvl==0)
	{
		nod->poz=x;
		return ;
	}
	lvl--;
	if (nod->a[(ind&(1<<lvl))>>lvl]==0)
	{
		nod->nrf++;
		nod->a[(ind&(1<<lvl))>>lvl]= new trie;
	}
	
	insert_tr(nod->a[(ind&(1<<lvl))>>lvl],lvl,x,ind);
}

int cauta(trie *nod, int lvl, int ind)
{
	if (lvl==0)
	{
		p=nod->poz;
		return 0;
	}
	lvl--;
	if (nod->a[1-((ind&(1<<lvl))>>lvl)])
		return cauta(nod->a[1-((ind&(1<<lvl))>>lvl)],lvl,ind)+1-((ind&(1<<lvl))>>lvl)<<lvl;
	else
		return cauta(nod->a[(ind&(1<<lvl))],lvl,ind)+(((ind&(1<<lvl)))>>lvl);
}

int main()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	insert_tr(rad,20,0,0);
	xx=0;
	inc=1;
	sf=1;
	max=0;
	for (i=1;i<=n;++i) 
	{
 	    scanf("%d", &x);
		xx^=x;
	    q=cauta(rad,20,xx);
		if ((xx^q)>max)
		{
			max=q^xx;
			inc=p+1;
			sf=i;
		}
		
		insert_tr(rad,20,i,xx);
	}
	
	printf("%d %d %d", max,inc,sf);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}