Cod sursa(job #330534)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 10 iulie 2009 14:14:25
Problema Xor Max Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <cstring>

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

struct trie
{
	int poz,nrf;
	trie *a[2];
	
	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 ((1^((ind&(1<<lvl))>>lvl))<<lvl)+cauta(nod->a[1^((ind&(1<<lvl))>>lvl)],lvl,ind);   
    else 
		return (ind&(1<<lvl))+cauta(nod->a[(ind&(1<<lvl))>>lvl],lvl,ind);   
}   



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=xx^q;
			inc=p+1;
			sf=i;
		}
		
		insert_tr(rad,20,i,xx);
	}
	
	printf("%d %d %d", max,inc,sf);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}