Cod sursa(job #978748)

Utilizator Kira96Denis Mita Kira96 Data 29 iulie 2013 16:54:59
Problema Xor Max Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int A,x,st,dr,poz,pot,cur,j,S,a,t,n,best,i;
char s[30];
struct Trie
{
	int po;
	Trie *fiu[2];
	Trie()
	{
		po=0;
		memset(fiu,0,sizeof(fiu));
	}
};
Trie *r=new Trie;
int find(Trie *nod,char *p)
{
	if(*p=='a')
		return 1;
	if(nod->fiu[*p]!=NULL)
		return find(nod->fiu[*p],p+1);
	return 0;
}
void insert(Trie *nod,char *p)
{
	if(*p=='a')
	{
		nod->po=i;
		return ;
	}
	if(nod->fiu[*p]==NULL)
	{
		nod->fiu[*p]=new Trie;
	}
	insert(nod->fiu[*p],p+1);
}
void solut(Trie *nod,char *p)
{
	pot>>=1;
	if(*p=='a')
	{
		poz=nod->po;
		return ;
	}
	if(nod->fiu[!(*p)]!=NULL)
	{
		A+=pot*(!(*p));
		solut(nod->fiu[!(*p)],p+1);
	}
	else
	{
		A+=pot*(*p);
		solut(nod->fiu[*p],p+1);
	}
}
int main ()
{
	f>>n;
	best=0;
	for(i=0;i<22;++i)
		s[i]=0;
	s[22]='a';
	insert(r,s);
	for(i=1;i<=n;++i)
	{
		f>>x;
		S^=x;
		a=S;
		t=-1;
		while(a)
		{
			t++;
			if(a&1)
				s[t]=1;
			else
				s[t]=0;
			a>>=1;
		}
		for(j=0;j<=10;++j)
			swap(s[j],s[21-j]);
		
		A=0;
		pot=(1<<22);
		solut(r,s);
		cur=A^S;
		if(cur>best)
		{ best=cur,st=poz,dr=i; }
		if(!find(r,s))
			insert(r,s);
		memset(s,0,22);
		if(S>best)
		{ best=S,st=0,dr=i; }
	}
	g<<best<<" "<<st+1<<" "<<dr;
	return 0;
}