Cod sursa(job #534116)

Utilizator ooctavTuchila Octavian ooctav Data 15 februarie 2011 11:13:05
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<cstdio>
#include<algorithm>
using namespace std;

#define FOR(i, a, b)	for(int i = a ; i <= b ; i++)

const int NMAX = 100005;
const int BMAX = 5;//23;

int N;
int a[NMAX];
int x[NMAX];
int c[BMAX], opus[BMAX];
int REZ;

struct trie
{
	bool e[2];
	trie *fiu[2];
	trie()
	{
		e[0] = e[1] = 0;
	}
};

trie *T = new trie;

void trans(int k)
{
	fill(c, c + BMAX, 0);
	int poz = BMAX - 1;
	while(k)	c[poz--] = k % 2, k /= 2;
}

void update(trie *nod, int poz)
{
	if(poz == BMAX)	return;
	if(!nod->e[c[poz]])	nod->e[c[poz]] = 1;
	nod->fiu[c[poz]] = new trie;
	
	update(nod->fiu[c[poz]], poz + 1);
}

void citi()
{
	scanf("%d", &N);
	FOR(i, 1, N)
	{	
		scanf("%d", &a[i]);
		x[i] = a[i] ^ x[i - 1];
		
		trans(x[i]);
		update(T, 0);
	}
}

void cauta_opus(trie *nod, int poz)
{
	if(!nod->e[0] && !nod->e[1])	return;
	if(nod->e[!c[poz]])	opus[poz] = !c[poz], cauta_opus(nod->fiu[c[poz]], poz + 1);
	else				opus[poz] = c[poz], cauta_opus(nod->fiu[c[poz]], poz + 1);
}

int sau()
{
	int sol = 0;
	FOR(i, 1, BMAX - 1)	
		sol = 2*sol + (c[i]^opus[i]);
	return sol;
}

int main()
{
	freopen("xormax.in", "r", stdin);
	freopen("xormax.out", "w", stdout);
	citi();
	FOR(i, 1, N)
	{
		trans(x[i]);
		cauta_opus(T, 0);
		REZ = max(REZ, sau());
	}
	printf("%d\n", REZ);
	return 0;
}