Cod sursa(job #142632)

Utilizator raula_sanChis Raoul raula_san Data 24 februarie 2008 20:44:48
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>

#define dim 100001
#define cnst 10

int A[dim], Trie[cnst*dim][2], T[cnst*dim];
int N;
int M;
int X;
int Nst;

void BagaTrie(int v, int i)
{
	int b, nb, x, st = 0;
	
	nb = M - 1;
	while(nb >= 0)
	{
		b = (v >> nb) & 1;
		if(!Trie[st][b])
		{
			Trie[st][b] = ++ Nst;
			st = Nst;
		}
		else
			st = Trie[st][b];
		-- nb;
	}
	T[st] = i;
}

int Query(int v)
{
	int st, nb, ret = 0;
	
	nb = M - 1;
	st = 0;
	while(nb >= 0)
	{
		int b = (v >> nb) & 1;
		if(Trie[st][!b])
		{
			ret |= (1 << nb);
			st = Trie[st][!b];
		}
		else
			st = Trie[st][b];
		-- nb;
	}
	X = st;
	return ret;
}

int main()
{
	freopen("xormax.in", "rt", stdin);
	freopen("xormax.out", "wt", stdout);

	int i;
	int v;
	int nb;
	int max;
	int imax;
	int jmax;

	for(scanf("%d", &N), i=1; i<=N; ++i)
	{
		scanf("%d", &v);
		A[i] = A[i-1] ^ v;

		v = A[i];
		nb = 0;
		while(v) ++ nb, v >>= 1;

		M = nb > M ? nb : M;
	}

	for(i=1; i<=N; ++i) BagaTrie(A[i], i);
	for(i=1, max=0; i<=N; ++i)
	{
		v = Query(A[i]);
		if(v > max) max = v, imax = i + 1, jmax = X;
	}

	printf("%d %d %d", max, imax, T[jmax]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}