Cod sursa(job #419001)

Utilizator FlorianFlorian Marcu Florian Data 16 martie 2010 20:11:11
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
using namespace std;
#include<fstream>
const int MAX_N = 100007;
int A[MAX_N], S[MAX_N], N, B = 25;
struct Trie
{
	int j;
	Trie *f[2];
	Trie()
	{
		f[0] = f[1] = 0;
		j = 0;
	}
};
Trie *T; int j;
void cauta(Trie *T, int k, int X)
{
	if( !T->f[0] && !T->f[1] ) { j = T->j;  return; }
	int x;
	if( (1<<k) & X) x = 1;
	else x = 0;
	if(T->f[1-x]) cauta(T->f[1-x], k - 1, X);
	else cauta(T->f[x], k - 1, X);
}
void insert(Trie *T, int k, int i)
{
	int x;
	if( (1<<k) & S[i]) x = 1;
	else x = 0;
	if( ! T->f[x] ) T->f[x] = new Trie;
	if(k == 0) T->f[x]->j = i;
	else insert(T->f[x], k - 1, i);
}
int main()
{
	ifstream in("xormax.in"); ofstream out("xormax.out");
	in>>N;
	int i, sol = 0, start, stop;
	for(i = 1; i <= N; ++i)
		in>>A[i];
	T = new Trie;
	sol = A[1], start = 1, stop = 1;
	insert( T, B, 0);
	for(i = 1; i <= N; ++i)
	{
		S[i] = S[i-1] ^ A[i];
		cauta( T, B, S[i] );
		if( (S[i] ^ S[j]) > sol)
		{
			sol = S[i] ^ S[j];
			start = j + 1;
			stop = i;
		}
		insert(T, B, i);
	}
	out<<sol<<" "<<start<<" "<<stop<<"\n";
	return 0;
}