Cod sursa(job #978764)

Utilizator Kira96Denis Mita Kira96 Data 29 iulie 2013 17:21:59
Problema Xor Max Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<fstream>
#include<cstring>
#define c *p
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(c=='a')
	{
		if(nod->po)
		return 1;
		return 0;
	}
	if(nod->fiu[c]!=NULL)
		return find(nod->fiu[c],p+1);
	return 0;
}
void insert(Trie *nod,char *p)
{
	if(c=='a')
	{
		nod->po=i;
		return ;
	}
	if(nod->fiu[c]==NULL)
	{
		nod->fiu[c]=new Trie;
	}
	insert(nod->fiu[c],p+1);
}
void solut(Trie *nod,char *p)
{
	pot>>=1;
	if(c=='a')
	{
		poz=nod->po;
		return ;
	}
	if(nod->fiu[!c]!=NULL)
	{
		A|=pot*(!c);
		solut(nod->fiu[!c],p+1);
	}
	else
	{
		A|=pot*c;
		solut(nod->fiu[c],p+1);
	}
}
int main ()
{
	f>>n;
	s[23]='a';
	i=0;
	insert(r,s);
	best=-1;
	for(i=1;i<=n;++i)
	{
		f>>x;
		S^=x;
		a=S;
		t=-1;
		while(a)
		{
			t++;
			if(a&1)
				s[t]=1;
			a>>=1;
		}
		for(j=0;j<=11;++j)
			swap(s[j],s[22-j]);
		A=0;
		pot=(1<<23);
		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,23);
	}
	g<<best<<" "<<st+1<<" "<<dr;
	return 0;
}