Cod sursa(job #575888)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 8 aprilie 2011 20:43:18
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#define NMAX 100005
int n,A[NMAX],act,sum[NMAX],best[NMAX],ant[NMAX];
int rez=-1,st,dr;
struct trie
{
	int cnt;
	trie *fiu[2];
	trie()
	{
		cnt=0;
		fiu[0]=fiu[1]=0;
	}
};
trie *T=new trie;
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&A[i]);
}
void ins(trie *nod,int val,int poz)
{
	if (poz==0)
	{
		nod->cnt=act;
		return ;
	}
	int tip=val & 1<<(poz-1);
	if (tip)
		tip=1;
	if (nod->fiu[tip]==0)
		nod->fiu[tip]=new trie;
	ins(nod->fiu[tip],val,poz-1);
}
void answer(trie *nod,int val,int poz)
{
	if (poz==0)
	{
		ant[act]=nod->cnt;
		return ;
	}
	if (nod->fiu[0]==0 && nod->fiu[1]==0)
		return ;
	int tip=val & 1<<(poz-1);
	if (tip)
		tip=1;
	if (nod->fiu[1 ^ tip])
		tip=1 ^ tip;
	answer(nod->fiu[tip],val,poz-1);
}
void solve()
{
	int i;
	ins(T,sum[0],22);
	for (i=1; i<=n; i++)
	{
		act=i;
		sum[i]=sum[i-1] ^ A[i];
		answer(T,sum[i],22);
		best[i]=sum[i] ^ sum[ant[i]];
		if (rez<best[i])
			rez=best[i], st=ant[i]+1, dr=i;
		ins(T,sum[i],22);
	}
}
int main()
{
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	read();
	solve();
	printf("%d %d %d\n",rez,st,dr);
	return 0;
}