Cod sursa(job #703514)

Utilizator eukristianCristian L. eukristian Data 2 martie 2012 12:42:27
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#define WIDTH 30

struct trie {
	int key;
	trie *b0, *b1;
	trie() {
		key = 0;
		b0 = b1 = 0x0;
	};
};

trie *T = new trie;
int n, returnValDS;

void insert(int nr, int pos)
{
	trie *crtNode = T;
	for (int i = WIDTH - 1; i >= 0 ; --i)
	{
		if (nr & (1 << i))
		{
			if (!crtNode->b1)
				crtNode->b1 = new trie;
			crtNode = crtNode->b1;
		}
		else
		{
			if (!crtNode->b0)
				crtNode->b0 = new trie;
			crtNode = crtNode->b0;
		}
	}
	
	crtNode->key = pos;
}

int find(int dw)
{
	trie *crtNode = T;
	int val = 0;
	
	for (int i = WIDTH - 1 ; i >= 0 ; --i)
	{
		if ((dw & (1 << i)) && crtNode->b0)
			crtNode = crtNode->b0;
		else if (crtNode->b1)
		{
			crtNode = crtNode->b1;
			val |= 1;
		}
		else
			crtNode = crtNode->b0;
			
		val <<= 1;
	}
	val >>= 1;
	returnValDS = val;
	return crtNode->key;
} 

int main()
{
	int tmp, x, crtXor = 0, bestStart = 1, bestStop = 1, max = -1;
	freopen("xormax.in", "r", stdin);
	scanf("%d", &n);
	
	insert(0, 0);
	for (int i = 1 ; i <= n ; ++i)
	{
		scanf("%d", &x);
		crtXor ^= x;
		
		int pos = find(crtXor);
		insert(crtXor, i);
		if ((returnValDS ^ crtXor) > max)
		{
			max = returnValDS ^ crtXor;
			bestStart = pos + 1;
			bestStop = i;
		}
		else if ((returnValDS ^ crtXor) == max && (i - pos) < bestStop - bestStart + 1)
		{
			bestStart = pos + 1;
			bestStop = i;
		}
	}
	
	freopen("xormax.out", "w", stdout);
	printf("%d %d %d\n", max, bestStart, bestStop);
	
	return 0;
}