Cod sursa(job #712103)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 13 martie 2012 01:36:29
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>

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

int n, sp[100002], last[2100000];

void add_trie (trie *t, int x, int p, int i)
{
	if (p < 0)
		return;
	
	int bit = (x & (1 << p)) > 0;
	
	if (!t -> fiu[bit])
		t -> fiu[bit] = new trie;
	add_trie (t -> fiu[bit], x, p - 1, i);
}

int find_trie (trie *t, int x, int p)
{
	if (p < 0)
		return 0;
	
	int bit = (x & (1 << p)) > 0;
	
	if (!bit)
	{
		if (t -> fiu[1])
			return find_trie (t -> fiu[1], x, p - 1) + (1 << p);
		else
			return find_trie (t -> fiu[0], x, p - 1);
	}
	else
	{
		if (t -> fiu[0])
			return find_trie (t -> fiu[0], x, p - 1);
		else
			return find_trie (t -> fiu[1], x, p - 1) + (1 << p);
	}
}

int main ()
{
	freopen ("xormax.in", "r", stdin);
	freopen ("xormax.out", "w", stdout);
	
	scanf ("%d", &n);
	
	trie *t = new trie;
	add_trie (t, 0, 20, 0);
	
	int i, x, y = 0, max = -1, st, dr;
	for (i = 1; i <= n; i ++)
	{
		scanf ("%d", &x);
		sp[i] = sp[i - 1] ^ x;
		
		if (i > 1)
			y = find_trie (t, sp[i], 20);
		
		if ((y ^ sp[i]) > max)
		{
			max = y ^ sp[i];
			st = last[y] + 1;
			dr = i;
		}
		
		last[sp[i]] = i;
		add_trie (t, sp[i], 20, i);
	}
	
	printf ("%d %d %d\n", max, st, dr);
	return 0;
}