Cod sursa(job #591036)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 21 mai 2011 22:29:45
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <vector>
using namespace std;
#define l 2

vector <vector <pair <int, int> > > v;
vector <int> trie;
int n, sol, r1, r2;

int getNext(int root, int c)
{
	int i;
	for (i=0; i<v[root].size(); i++)
		if (v[root][i].first==c) return v[root][i].second;
	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=trie.size();
			trie.push_back(p);
			v.resize(trie.size());
			v[root].push_back(make_pair(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;
	trie.resize(1);
	v.resize(1);
	for (i=1; i<=n; i++)
	{
		scanf("%d", &x);
		s^=x;
		if (i>1) search(s, i);
		addTrie(s, i);
	}
	printf("%d %d %d\n",sol, r1, r2);
}