Cod sursa(job #354916)

Utilizator hadesgamesTache Alexandru hadesgames Data 9 octombrie 2009 21:17:49
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define mp make_pair
#define fi first
#define se second
long long put[30];
struct nod
{
	nod * v[2];
	int indice;
};
nod * trie;
FILE *in,*out;
int nr,sol[40];
pair<long long,long long> cauta(long long x,long long  adancime,nod  * me)
{
//	fprintf(stderr,"intra in cauta\n");
	if (adancime==21)
		return mp(0,me->indice);
	bool next=!(x&put[adancime+1]);
	if (next&&me->v[1]==NULL)
	{
		//fprintf(stderr,"Schimba din 1 in 0\n");
		next=0;
	}
	else
		if (!next&&me->v[0]==NULL)
		{
			//fprintf(stderr,"Schimba din 0 in 1\n");
			next=1;
		}
	if (me->v[next]==NULL)
	{
		//fprintf(stderr,"hmmm SA blocat");
		return mp(0,0);
	}
	//fprintf(stderr,"Adancime %d next= %d\n",adancime,next);
	pair <long long,long long> aux=cauta(x,adancime+1,me->v[next]);
//	fprintf(stderr,"iese din cauta\n");
	return mp(put[adancime+1]*next+aux.fi,aux.se);
}
void adauga(long long x,long long  adancime,long long indice,nod * me)
{
	//fprintf(out,"Intra in adauga %lld %lld\n",x,adancime);
//
//	fprintf(stderr,"intra in adauga\n");
	bool next;
	if (adancime==21)
	{
		me->indice=indice;
		return ;
	}
	next=x&put[adancime+1];
	if (me->v[next]==NULL)
	{
		me->v[next]=new nod;
		me->v[next]->v[0]=me->v[next]->v[1]=NULL;
	}
	//fprintf(out," Adancime %lld => %lld %lld %lld\n",adancime,next,x,put[adancime+1]);
	//fprintf(stderr,"iese din adauga");
	adauga(x,adancime+1,indice,me->v[next]);
}
/*
void dfs_ver(nod * me)
{
	nr++;
	int i;
	if (nr==21)
	{
		for(i=1;i<=21;i++)
			fprintf(out,"%d",sol[i]);
		fprintf(out,"\n");
		return ;
	}
	for(i=0;i<=1;i++)
		if (me->v[i]!=NULL)
		{
			sol[nr]=i;
			dfs_ver(me->v[i]);
		}
	nr--;
		
}*/
int main()
{
	long long n,i,maxv=-1,x,partial,start,stop;
//	fprintf(stderr,"Point 1\n");
	in=fopen("xormax.in","r");
	out=fopen("xormax.out","w");
	//fprintf(stderr,"Point 1\n");
	fscanf(in,"%lld",&n);
	trie=new nod;
	trie->v[0]=trie->v[1]=NULL;
	put[21]=1;
	for(i=20;i>=1;i--)
		put[i]=2*put[i+1];
	partial=0;
	adauga(0,0,0,trie);
	maxv=-3;
	for(i=1;i<=n;i++)
	{
		fscanf(in,"%lld",&x);
		partial=partial xor x;
		pair <long,long> aux=cauta(partial,0,trie);
		if (partial xor aux.fi>maxv)
		{
			maxv=aux.fi xor partial;
			start=aux.se+1;
			stop=i;
		}
		adauga(partial,0,i,trie);
	//	printf("%d\n",aux.fi);
	}
	//dfs_ver(trie);
	//fprintf(stderr,"Point 1\n");
	fprintf(out,"%lld %lld %lld\n",maxv,start,stop);
	fclose(in);
	fclose(out);
	return 0;
}