Cod sursa(job #218693)

Utilizator razvan2006razvan brezulianu razvan2006 Data 3 noiembrie 2008 08:46:34
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <math.h>

#define MAXN 100001
#define cnt 10

long n, m, nst, pos, xmax, imax, jmax, lmin, a[MAXN], t[MAXN * cnt], TRIE[MAXN * cnt][2], i, v, nb;

long Query(long v) {
	long b, nb, ret, st;
	for (ret = st = 0, nb = m - 1; nb >= 0; --nb) {
		b = (v >> nb) & 1;
		if (TRIE[st][!b]) {
			ret |= (1 << nb);
			st = TRIE[st][!b];
		} else {
			st = TRIE[st][b];
		}
	}
	pos = st;
	return ret;
}

void BagaTrie(long v, long pos) {
	long st = 0, nb, b;
	for (nb = m - 1; nb >= 0; --nb) {
		b = (v >> nb) & 1;
		if(!TRIE[st][b]) {
			TRIE[st][b] = ++nst;
			st = nst;
		} else {
			st = TRIE[st][b];
		}
	}
	if(!t[st]) {
		t[st] = pos;
	}
}

void Build() {
	for (long i = 1; i <= n; ++i) {
		BagaTrie(a[i], i);
	}
	BagaTrie(0, 0);
}

int main() {
	freopen("xormax.in", "r", stdin);
	freopen("xormax.out", "w", stdout);
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &v);
		a[i] = a[i - 1] ^ v;
		nb = 1;
		while(v) {
			++nb; 
			v >>= 1;
		}
		m = nb > m ? nb : m;
	}
	Build();
	for (i = 0, xmax = -1; i < n; ++i) {
		v = Query(a[i]);
		if (t[pos] <= i) continue;
		if (v > xmax) {
			xmax = v;
			imax = i + 1;
			jmax = t[pos];
			lmin = jmax - i;
		} else { 
			if(v == xmax && t[pos] < jmax) {
				imax = i + 1;
				jmax = t[pos];
				lmin = jmax - i;
			} else {
				if (v == xmax && t[pos] == jmax && t[pos] - i < lmin) {
					imax = i + 1;
					lmin = t[pos] - i;
				}
			}
		}
	}
	printf("%ld %ld %ld", xmax, imax, jmax);
	return 0;
}