Cod sursa(job #519701)

Utilizator kmadaUngur Oana Madalina kmada Data 6 ianuarie 2011 11:58:52
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <string>

using namespace std;

#define TM 1000005
#define NM 100005

int trie[TM][2], C[TM], noduri;

int A[NM], op, pop;

int insereaza (int numar, int poz)
{
	int p = 20;

	int nod = 0, digit;

	while (p >= 0)
	{
		if ((1<<p) & numar) digit = 1;
		else digit = 0;

		if (!trie[nod][digit])
		{
			++noduri;
			trie[nod][digit] = noduri;
		}

		nod = trie[nod][digit];

		--p;
	}

	C[nod] = poz;
}

void cauta (int numar)
{
	op = 0;

	int p = 20;

	int nod = 0, digit;

	while (p >= 0)
	{
		if ((1<<p) & numar) digit = 0;
		else digit = 1;

		if (trie[nod][digit])
		{
			op += digit * (1<<p);
			nod = trie[nod][digit];
		}
		else
		{
			op += (1-digit) * (1<<p);
			nod = trie[nod][1-digit];
		}

		--p;
	}

	pop = C[nod];
}

int main()
{
	int best = -1, st, dr, N;

	freopen ("xormax.in", "r", stdin);
	freopen ("xormax.out", "w", stdout);

	scanf ("%d", &N);

	for (int i = 1; i <= N; ++i) scanf ("%d", &A[i]);

	int sum_xor = 0;

	insereaza (sum_xor, 0);

	for (int i = 1; i <= N; ++i)
	{
		sum_xor = sum_xor ^ A[i];

		cauta (sum_xor);

		insereaza (sum_xor, i);

		if ((op^sum_xor) > best)
		{
			best = op^sum_xor;
			dr = i;
			st = pop + 1;
		}

		//printf ("%d ", op^sum_xor);
	}

	//printf ("\n");
	printf ("%d %d %d", best, st, dr);

	return 0;
}