Cod sursa(job #282175)

Utilizator rupraRupra C rupra Data 17 martie 2009 00:17:14
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <algorithm>
#include <stdio.h>

using namespace std;

class NodTrie
{
	public:
		int poz, nrFii;
		NodTrie *fii[2];

		NodTrie()
		{
			memset(fii, 0, sizeof(fii));
			poz = nrFii = 0;
		}
};

NodTrie *radTrie = new NodTrie;
int n, sumXor, start = 1, finish = 1, maxGs, locGs;

void addTrie(NodTrie *nod, int level, int key, int place)
{
	if (!level)
	{
		nod->poz = place;
		return;
	}

	level--;
	if (!nod->fii[(key & (1 << level)) >> level])
	{
		nod->nrFii++;
		nod->fii[(key & (1 << level)) >> level] = new NodTrie;
	}

	addTrie(nod->fii[(key & (1 << level)) >> level], level, key, place);
}

int cautaOpus(NodTrie *nod, int level, int key)
{
	if (!level)
	{
		locGs = nod->poz;
		
		return 0;
	}

	level--;
	if (nod->fii[1 ^ ((key & (1 << level)) >> level)])
		return ((1 ^ ((key & (1 << level)) >> level)) << level) + cautaOpus(nod->fii[1 ^ ((key & (1 << level)) >> level)], level, key);
	else return (key & (1 << level)) + cautaOpus(nod->fii[(key & (1 << level)) >> level], level, key);
}

int main()
{
	freopen("xormax.in", "r", stdin);
	freopen("xormax.out", "w", stdout);

	scanf("%d", &n);

	addTrie(radTrie, 24, 0, 0);
	for (int i = 1; i <= n; i++)
	{
		int elem;
		scanf("%d", &elem);

		sumXor ^= elem;
		int valMax = cautaOpus(radTrie, 24, sumXor);
		if (maxGs < (sumXor ^ valMax))
		{
			maxGs = (sumXor ^ valMax);
			start = locGs + 1;
			finish = i;
		}

		addTrie(radTrie, 24, sumXor, i);
	}

	printf("%d %d %d\n", maxGs, start, finish);

	fclose(stdin);
	fclose(stdout);
	return 0;
}