Cod sursa(job #534339)

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

const int NMAX = 100005;
const int BMAX = 25;

int N;
int a[NMAX];
int x[NMAX];
int c[BMAX + 2], opus[BMAX + 2];
int REZ;
int i;
int Y;
int v1, v2;

struct trie
{
	trie *fiu[2];
	int term;
	trie()
	{
		fiu[0] = fiu[1] = 0;
		term = 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 - 1)	
	{if(nod->term == 0)nod->term = i; 
	return;}
	if(nod->fiu[c[poz]] == 0)	nod->fiu[c[poz]] = new trie;
	
	update(nod->fiu[c[poz]], poz + 1);
}

void citi()
{
	scanf("%d", &N);
	update(T, 0);
	for(i = 1 ; i <= N ; i++)
	{	
		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->fiu[0] == 0 && nod->fiu[1] == 0)	{Y = nod->term; return;}
	if(nod->fiu[!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(int j = 0 ; j < BMAX ; j++)
		sol = 2*sol + (c[j]^opus[j]);
	return sol;
}

int main()
{
	freopen("xormax.in", "r", stdin);
	freopen("xormax.out", "w", stdout);
	citi();
	
	for(i = 1 ; i <= N ; i++)
	{
		trans(x[i]);
		cauta_opus(T, 0);
		int k = sau();
		if(REZ < k)
		{
			REZ = k;
			v1 = i + 1;//min(i, Y) + 1;
			v2 = Y;//max(i, Y);
		}
	}
	printf("%d %d %d\n", REZ, v1, v2);
	return 0;
}