Cod sursa(job #491245)

Utilizator hadesgamesTache Alexandru hadesgames Data 10 octombrie 2010 19:40:26
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
FILE *in,*out;
struct nod
{
	int v;
	nod * next[2];
	nod()
	{
		next[0]=next[1]=NULL;
		v=0;
	}
};
nod * trie;
void add( nod * p, int val,int poz,int adanc)
{
	if (adanc<0)
	{
		p->v=poz;
		if (val!=0)
			fprintf(stderr,"bug\n");
		return ;
	}
	int x=(bool)(val & (1<<adanc));
	if (p->next[x]==NULL)
		p->next[x]=new nod;
	add(p->next[x],val-(1<<adanc)*x,poz,adanc-1);
}
int search (nod * p, int &rez, int y,int adanc)
{
	if (adanc<0)
		return p->v;
	int x=!(y&(1<<adanc));
	if (p->next[x]!=NULL)
	{
		rez+=(1<<adanc)*x;
		return search(p->next[x],rez,y,adanc-1);
	}
	rez+=(1<<adanc)*(!x);
	return search(p->next[!x],rez,y,adanc-1);
}
int main()
{
	int n,y,i,x,start,stop,maxv,poz;
	in=fopen("xormax.in","r");
	out=fopen("xormax.out","w");
	fscanf(in,"%d",&n);
	trie=new nod;
	y=0;
	for (i=1;i<=n;i++)
	{
		fscanf(in,"%d",&x);
		y=y^x;
		add(trie,y,i,20);
		if (i==1)
		{
			maxv=y;
			start=0;
			stop=1;
			continue;
		}
		x=0;
		poz=search(trie,x,y,20);
		if ((x^y)>maxv)
		{
			maxv=x^y;
			start=poz;
			stop=i;
		}
	}
	fprintf(out,"%d %d %d\n",maxv,start+1,stop);
	fclose(in);
	fclose(out);
	return 0;

}