Cod sursa(job #200604)

Utilizator tvladTataranu Vlad tvlad Data 25 iulie 2008 09:02:58
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>

const int N_MAX = 100000;
const int E_MAX = 1000000;

int n, sz, max = 0, st, en;
int elem[E_MAX][3];
int v[N_MAX+1];

void insert ( int where, int what ) {
	int p, exp, bit;
	for (p = 0, exp = 1 << 20; exp; exp >>= 1) {
		bit = (where & exp) ? 1 : 0;
		if (elem[p][bit] == -1) {
			elem[sz][0] = elem[sz][1] = elem[sz][2] = -1;
			elem[p][bit] = sz;
			++sz;
		}
		p = elem[p][bit];
	}
	elem[p][2] = what;
}

int query ( int where ) {
	int p, exp, bit;
	for (p = 0, exp = 1 << 20; exp; exp >>= 1) {
		bit = (where & exp) ? 1 : 0;
		if (elem[p][!bit] != -1) {
			p = elem[p][!bit];
		} else
		if (elem[p][bit] != -1) {
			p = elem[p][bit];
		} else
			return -1;
	}
	return elem[p][2];
}

int main() {
	freopen("xormax.in","rt",stdin);
	freopen("xormax.out","wt",stdout);
	scanf("%d",&n);
	sz = 2;
	elem[0][0] = 1; elem[0][1] = elem[0][2] = -1;
	elem[1][0] = elem[1][1] = -1; elem[1][2] = 0;
	v[0] = 0;
	for (int i = 1, a, p; i <= n; ++i) {
		scanf("%d",&a);
		v[i] = v[i-1] ^ a;
		p = query(v[i]);
		if (p != -1) {
			if ((v[i] ^ v[p]) > max) {
				max = v[i] ^ v[p];
				st = p+1;
				en = i;
			}
		}
		insert(v[i],i);
	}
	printf("%d %d %d\n",max, st, en);
	return 0;
}