Cod sursa(job #350833)

Utilizator octavOctavian Voicu octav Data 26 septembrie 2009 01:45:44
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <string.h>

#define MAXN		100000
#define NBITS		21
#define MAXVAL		((1 << NBITS) - 1)
#define TRIESIZE	(1 << NBITS)

int A[MAXN];
int values[MAXN + 1];
int childs[TRIESIZE][2];
int lastval, lastnode;

void trieadd(int key, int val)
{
	int i, j, k;

	for (i = 0, j = NBITS - 1; j >= 0; j--) {
		k = (key >> j) & 1;
		if (!childs[i][k])
			childs[i][k] = j ? ++lastnode : ++lastval;
		i = childs[i][k];
	}

	values[i] = val;
}

int triequery(int *key)
{
	int i, j, k, key1, key2;

	key1 = *key;
	key2 = 0;
	for (i = 0, j = NBITS - 1; j >= 0; j--) {
		k = (key1 >> j) & 1;
		if (childs[i][k]) {
			i = childs[i][k];
			if (k)
				key2 |= 1 << j;
		} else {
			i = childs[i][1 - k];
			if (!k)
				key2 |= 1 << j;
		}
	}

	*key = key2;

	return values[i];
}

int main()
{
	int N;
	int bestxor, beststart, bestend;
	int i, j, x, y;

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

	scanf("%d", &N);

	for (i = 0; i < N; i++)
		scanf("%d", A + i);

	bestxor = A[0];
	beststart = bestend = 0;

	trieadd(0, -1);
	x = 0;
	for (i = 0; i < N; i++) {
		x ^= A[i];
		y = x ^ MAXVAL;
		j = triequery(&y);
		y ^= x;
		if (bestxor < y) {
			bestxor = y;
			beststart = j + 1;
			bestend = i;
		}
		trieadd(x, i);
	}

	printf("%d %d %d\n", bestxor, beststart + 1, bestend + 1);

	return 0;
}