Cod sursa(job #484817)

Utilizator ZethpixZethpix Zethpix Data 15 septembrie 2010 22:33:29
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>

long long n,s,x,y,max,pos,l,r;
long i;

struct trie
{
	int nr;
	trie *link[2];
}*t;

void add(long long x,long w)
{
	trie *p;
	long i,b;
	p=t;

	for(i=20;i>=0;i--)
	{
		b=x&(1<<i);
		b=b>>(1<<(i-1));
		if(p->link[b]==NULL)
		{
			p->link[b]=new trie;
			p->link[b]->link[0]=NULL;
			p->link[b]->link[1]=NULL;
		}
		p=p->link[b];
	}
	p->nr=w;
}

long long find(long long x)
{
	trie *p;
	p=t;
	long long y=0;
	long i,b;

	for(i=20;i>=0;i--)
	{
		b=x&(1<<i);
		b=b>>(1<<(i-1));
		if(p->link[1-b]!=NULL)
		{
			if(b==0) y=y|(1<<i);
			p=p->link[1-b];
		}
		else
		{
			if(b==1) y=y|(1<<i);
			p=p->link[b];
		}
	}
	pos=p->nr;

	return y;
}

int main()
{
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);

	scanf("%lld%lld",&n,&s);
	t=new trie;
	t->link[0]=NULL;
	t->link[1]=NULL;
	add(s,1);
	max=0;
	l=0;
	r=0;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		pos=1;
		y=find(x);
 		if(x^y>max)
		{
			max=x^y;
			l=pos;
			r=i;
		}
		s^=x;
		add(s,i);
	}

	printf("%lld %lld %lld",max,l,r);
	return 0;
}