Cod sursa(job #484858)

Utilizator ZethpixZethpix Zethpix Data 16 septembrie 2010 08:03:34
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

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

int x,s,n,i,max,l,r,pos;

void con(tre *&p)
{
	p=new tre;
	p->link[0]=NULL;
	p->link[1]=NULL;
}

void add(int x,int c)
{
	int i,b;
	tre *at;
	at=t;

	for(i=22;i>0;i--)
	{
		b=(x&(1<<(i-1)))>>(i-1);
		if(at->link[b]==NULL)
			con(at->link[b]);
		at=at->link[b];
	}
	at->nr=c;
}

int src(int x)
{
	int i,b,y=0;
	tre *at;
	at=t;

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

	return y;
}

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

	scanf("%d%d",&n,&s);
	con(t);
	add(x,1);
	add(0,0);
	for(i=2;i<=n;i++)
	{
		scanf("%d",&x);
		s^=x;
		x=src(s);
		if((s^x)>max)
		{
			max=s^x;
			l=pos;
			r=i;
		}
		add(s,i);
	}

	printf("%d %d %d\n",max,l+1,r);

	return 0;
}