Cod sursa(job #469869)

Utilizator APOCALYPTODragos APOCALYPTO Data 9 iulie 2010 14:03:15
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
using namespace std;

const char iname[] = "xormax.in";
const char oname[] = "xormax.out";
const int  MaxN = 100001;

int  N;
int  X[MaxN];
int  A[2 * 2097152];
bool B[2 * 2097152];


#define left  (2 * n)
#define right (2 * n + 1)

void update(int n, int p, int k)
{
	if (k == -1) {
		A[n] = p;
		B[n] = true;
	} else {
		if (X[p] & (1 << k))
			update(right, p, k - 1);
		else
			update(left, p, k - 1);
		B[n] = (B[left] || B[right]);
	}
}

int query(int n, int m, int k)
{
	if (k == -1)
		return A[n];
	if (((m & (1 << k)) && B[left] == true))
		return  query(left, m, k - 1);
	return  query(right, m, k - 1);
}

int main(void)
{
	int i;
	int best, l, r;
	int temp, p;
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);

	scanf("%d\n", &N);
	for (i = 1; i <= N; ++i)
		scanf("%d ", X + i), X[i] ^= X[i - 1];

	best = -1;
	update(1, 0, 20);
	for (i = 1; i <= N; ++i) {
		p = query(1, X[i], 20);
		temp = X[i] ^ X[p];
		if (best < temp)
			best = temp, l = p, r = i;
		update(1, i, 20);
	}
	printf("%d %d %d\n", best, l + 1, r);

	return 0;
}