Cod sursa(job #142679)

Utilizator raula_sanChis Raoul raula_san Data 24 februarie 2008 21:59:10
Problema Xor Max Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 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, 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;
	}
	if(!T[st]) 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 = 0;
	int imax = 0;
	int jmax = 0;
	int lmin = N + 1;

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

		if(v > max) max = v, imax = i, jmax = i, lmin = 1;

		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);
	
		if(A[i] > max) max = A[i], imax = 1, jmax = i, lmin = i;
	}
	
	for(i=1; i<N; ++i)
	{
		v = Query(A[i]);
		
		if(T[X] > i)
		{
		if(v > max) max = v, imax = i + 1, jmax = T[X], lmin = T[X] - i;
		else if(v == max && T[X] < jmax) imax = i + 1, jmax = T[X], lmin = T[X] - i;
		else if(v == max && T[X] == jmax && T[X]-i < lmin) imax = i + 1, jmax = T[X], lmin = T[X] - i;
		}
	}

	int smax = 0;
	for(i=0; i<N; ++i)
		for(int j=i+1; j<=N; ++j)
		{
			int s = A[j] ^ A[i];
			if(smax < s) smax = s;
		}

	if(max != smax) for(;;);
	printf("%d %d %d", max, imax, jmax);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}