Cod sursa(job #575718)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 8 aprilie 2011 17:57:33
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <string>
#include <cstring>

#define maxn 100010
using namespace std;

struct trie 
{
	int ret;
	trie *fiu[2];
	trie () 
	{	
		ret = 0;
		fiu[0] = 0;
		fiu[1] = 0;
	}
};
trie *T = new trie;

int i, n, ans = -1, px, py, A, X[maxn];
void insert (trie *nod, int x, int bit)
{
	if (bit == -1) 
	{
		nod -> ret = i;
		return ;
	}
	bool vbit = (x & (1 << bit));

	if (nod -> fiu[vbit] == 0)
		nod -> fiu[vbit] = new trie;
	
	insert (nod -> fiu[vbit], x, bit - 1);
}
void query (int x, int bit)
{	
	trie *nod = T;

	while (bit != -1) {
		bool val = (x & (1 << bit));
		if (nod -> fiu[val ^ 1])
			nod = nod -> fiu[val ^ 1];
		else nod = nod -> fiu[val];
		bit--;
	}

	if ((x xor X[nod -> ret]) > ans) {
		ans = x xor X[nod -> ret];
		px = nod -> ret + 1;
		py = i;
	}
}
int main ()
{


	freopen ("xormax.in", "r", stdin);
	freopen ("xormax.out", "w", stdout);

	scanf ("%d\n", &n);
	
		
	insert (T, 0, 21);
	
	for (i = 1; i <= n; i++) {
	
		scanf ("%d", &A);
		
		X[i] = X[i - 1] xor A;
		
		query (X[i], 21);
		insert (T, A, 21);
	}
	printf ("%d %d %d\n", ans, px, py);

	return 0;
}