Cod sursa(job #513820)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 17 decembrie 2010 01:41:57
Problema Xor Max Scor 10
Compilator cpp Status done
Runda night_time_contest1 Marime 1.34 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 %d %d", best, st, dr);
	
	return 0;
}