Cod sursa(job #464827)

Utilizator AndreyPAndrei Poenaru AndreyP Data 21 iunie 2010 21:49:38
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#define N 100005

struct Nod
{
	Nod *v[2];
	Nod()
	{
		v[0]=v[1]=0;
	}
};
int n;
int a[N];
Nod *t=new Nod;
int xmax,start,stop;
const int M=1<<20;

inline void citire()
{
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
	{
		scanf("%d",&a[i]);
		a[i]^=a[i-1];
	}
}

void add(Nod *x,int nr,int mask)
{
	if(mask==0)
		return;
	if((nr&mask)==0)
	{
		if(x->v[0]==0)
			x->v[0]=new Nod;
		add(x->v[0],nr,mask>>1);
	}
	else
	{
		if(x->v[1]==0)
			x->v[1]=new Nod;
		add(x->v[1],nr,mask>>1);
	}
}

int find(Nod *x,int nr,int mask)
{
	if(mask==0)
		return 0;

	if((nr&mask)==0)
	{
		if(x->v[1]!=0)
			return (mask|find(x->v[1],nr,mask>>1));
		else
			return find(x->v[0],nr,mask>>1);
	}
	else
	{
		if(x->v[0]!=0)
			return (mask|find(x->v[0],nr,mask>>1));
		else
			return find(x->v[1],nr,mask>>1);
	}
}

inline void rezolva()
{
	add(t,0,M);
	int aux;
	for(int i=1; i<=n; ++i)
	{
		aux=find(t,a[i],M);
		if(aux>xmax)
		{
			xmax=aux;
			stop=i;
		}
		add(t,a[i],M);
	}

	if(xmax==0)
	{
		printf("0 1 1\n");
		return;
	}

	aux=xmax^a[stop];
	start=stop-1;
	for(; a[start]!=aux; --start)
		;

	++start;
	printf("%d %d %d\n",xmax,start,stop);
}

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

	citire();
	rezolva();

	return 0;
}