Cod sursa(job #591048)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 21 mai 2011 22:55:23
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#define l 20
#define lmax (1<<21)+3

int n, sol, r1, r2, v[lmax][2], trie[lmax], h;

int getNext(int root, int c)
{
	if (v[root][c]) return v[root][c];
	return -1;
}

void addTrie(int x, int p)
{
	int i, c, root=0, next;
	for (i=l; i>=0; i--)
	{
		c=x&(1<<i);
		if (c>0) c=1;
		next=getNext(root, c);
		if (next==-1)
		{
			next=h;
			h++;
			trie[h]=p;
			v[root][c]=next;
		} else trie[next]=p;
		root=next;
	}
}

void search(int x, int p)
{
	int i, c, root=0, next, sum=0;
	for (i=l; i>=0; i--)
	{
		c=x&(1<<i);
		if (c>0) c=1;
		c=!c;
		next=getNext(root, c);
		if (next==-1)
		{
			c=!c;
			next=getNext(root, c);
		} else sum+=(1<<i);
		root=next;
	}
	if (sum>sol)
	{
		sol=sum;
		r1=trie[root]+1;
		r2=p;
	}
}

int main()
{
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	scanf("%d", &n);
	int i, x, s=0;
	h=1;
	for (i=1; i<=n; i++)
	{
		scanf("%d", &x);
		s^=x;
		if (i>1) search(s, i); else
		{
			sol=x;
			r1=r2=i;
		}
		addTrie(s, i);
	}
	printf("%d %d %d\n",sol, r1, r2);
}