Cod sursa(job #127424)

Utilizator megabyteBarsan Paul megabyte Data 23 ianuarie 2008 21:24:35
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#define INF "xormax.in"
#define OUF "xormax.out"
#define NMAX 100002
#define PMAX 20
using namespace std;
int t[(1<<(PMAX+2))];

void insert(int x,int poz)// x=suma xor, poz= poz 
{
	int j,p;
	//printf("insert %d:\n",x);
	p=1;
	for(j=PMAX;j>=0;--j)
		if(x&(1<<j)) // bitul j este 1
		{
			//printf("1 ");
			t[p]=0;
			p=2*p+1;
		}
		else
		{
			//printf("0 ");
			t[p]=0;
			p=2*p;
		}
	//printf("\n");
	t[p]=poz;
}

int query(int x)//returneaza cea mai buna pozitie pentru suma xor x
{
	int j,p;
	p=1;
	for(j=PMAX;j>=0;--j)
		if(x&(1<<j))
		{
			if(t[2*p]>=0) p=2*p;
			else p=2*p+1;
		}
		else
		{
			if(t[2*p+1]>=0) p=2*p+1;
			else p=2*p;
		}
	if(t[p]>0) return t[p];
	return 0;
}

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int xsum[NMAX],x,i,n;
	int solsum,st,dr;
	fscanf(in,"%d",&n);

	for(i=0;i<(1<<PMAX+2);++i) t[i]=-1;

	xsum[0]=0;
	insert(0,0);

	fscanf(in,"%d",&x);
	insert(x,1);
	xsum[1]=x;
	solsum=x;st=1;dr=1;

	for(i=2;i<=n;++i)
	{
		fscanf(in,"%d",&x);

		xsum[i]=(xsum[i-1]^x);
		insert(xsum[i],i);

		x=0;
		x=query(xsum[i]);
//		printf("%d %d %d\n",i,x,(xsum[i]^xsum[x]));
		if((xsum[i]^xsum[x])>solsum)
		{
			solsum=(xsum[i]^xsum[x]);
			st=x+1;dr=i;
		}
	}

	//for(i=1;i<(1<<(PMAX+2));++i) printf("%d ",t[i]);

	fprintf(out,"%d %d %d\n",solsum,st,dr);
	fclose(in);fclose(out);
	return 0;
}