Cod sursa(job #703623)

Utilizator eukristianCristian L. eukristian Data 2 martie 2012 13:15:48
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#define WIDTH 22
struct trie {
	int key;
	trie *childs[2];
	trie() {
		key = 0;
		childs[0] = childs[1] = 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)
	{
		bool branch = nr & (1 << i);
		
		if (!crtNode->childs[branch])
			crtNode->childs[branch] = new trie;
		crtNode = crtNode->childs[branch];
	}
	
	crtNode->key = pos;
}

int find(int dw)
{
	trie *crtNode = T;
	int val = 0;
	
	for (int i = WIDTH - 1 ; i >= 0 ; --i)
	{
		bool branch = dw & (1 << i);
		if (crtNode->childs[!branch])
		{
			crtNode = crtNode->childs[!branch];
			val |= (!branch);
		}
		else
		{
			crtNode = crtNode->childs[branch];
			val |= branch;
		}
		
		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);
		
		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;
		}
		
		insert(crtXor, i);
	}
	
	freopen("xormax.out", "w", stdout);
	printf("%d %d %d\n", max, bestStart, bestStop);
	
	return 0;
}