Cod sursa(job #513823)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 17 decembrie 2010 02:00:05
Problema Xor Max Scor 100
Compilator cpp Status done
Runda night_time_contest1 Marime 1.4 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;
}