Cod sursa(job #26100)

Utilizator pantaniMarco Pantani pantani Data 5 martie 2007 10:34:49
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>

#define Nmax 100005
#define Hmax 21

struct trie
{
	trie() : st(NULL), dr(NULL), par(0){}
	int par;
	trie *st, *dr;
};

int best = -1, n, a1, b1;
int v[Nmax];
trie *cap;

void readdata()
{
	freopen("xormax.in", "r", stdin);
	freopen("xormax.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &v[i]);
}

void build(int k, int pas)
{
	trie *cur = cap;
	int i;
	
	for (int i = 20; i >= 0; --i)
		if ((k >> i) & 1)
			cur = cur->dr == NULL ? cur->dr = new trie : cur->dr;
		else
			cur = cur->st == NULL ? cur->st = new trie : cur->st;
	cur->par = pas;
}

void eval(int k, int &rez, int &pz)
{
	trie *cur = cap;
	int i;
	
	rez = 0;
	for (i = 20; i >= 0; --i)
		if ((k >> i) & 1)
		{
			if (cur->st != NULL)
			{
				cur = cur->st;
				rez |= 1 << i;
			}
			else cur = cur->dr;
		}
		else
		{
			if (cur->dr != NULL)
			{
				cur = cur->dr;
				rez |= 1 << i;
			}
			else cur = cur->st;
		}
	pz = cur->par;
}

void solve()
{
	int i, val = 0, aux, pz;
	
	cap = new trie;
	build(0, 0);
	
	for (i = 1; i <= n; ++i)
	{
		val ^= v[i];
		eval(val, aux, pz);
		if (aux > best)
		{
			best = aux;
			a1 = pz;
			b1 = i;
		}
		build(val, i);
	}
	printf("%d %d %d\n", best, a1+1, b1);
}

int main()
{
	readdata();
	solve();
	return 0;
}