Cod sursa(job #429674)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 30 martie 2010 13:04:49
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>

#define NMAX 100100
#define BMAX 23
using namespace std;

struct Trie
{
	int L;
	Trie* f[2];
	
	Trie()
	{
		f[0] = f[1] = 0;
		L = 0;
	}
};
Trie* T;

int N, A[NMAX], best, bestI, bestJ, Sum[NMAX], j;


void readAll(void)
{
	ifstream fin("xormax.in");
	
	fin >>N;
	
	for (int i = 1; i <= N; i++)
		fin >>A[i];
	
	fin.close();
}

void Cauta(Trie* T, int B, int Nr)
{
	if (!T->f[0] && !T->f[1] ) {j = T->L; return;}
	
	int x = 0;
	if ( (1 << B) & Nr ) x = 1;
	
	if ( T->f[1-x] ) Cauta(T->f[1-x], B-1, Nr);
	else Cauta(T->f[x], B-1, Nr);
}

void Add(Trie* T, int B, int Nr, int Ind)
{
	int x = 0;
	if ( (1 << B) & Nr ) x = 1;
	
	if (!T->f[x]) T->f[x] = new Trie;
	
	if (B == 0) T->f[x]->L = Ind;
	else Add(T->f[x], B - 1, Nr, Ind);
}

void Solve(void)
{
	int i;
	
	T = new Trie;
	
	for (i = 1; i <= N; i++)
	{
		Sum[i] = Sum[i-1] ^ A[i];
		
		Cauta(T, BMAX, Sum[i]); 
		
		if ( (Sum[i] ^ Sum[j]) > best)
		{
			best = Sum[i] ^ Sum[j];
			bestI = i;
			bestJ = j;
		}
		Add(T, BMAX, Sum[i], i);
	}
}

void writeAll(void)
{
	ofstream fout("xormax.out");
	
	fout <<best <<' '<<bestJ + 1 <<' '<<bestI <<'\n';
	
	fout.close();
}

int main()
{
	readAll();
	
	Solve();

	writeAll();
	
	return 0;
}