Cod sursa(job #601833)

Utilizator Catah15Catalin Haidau Catah15 Data 7 iulie 2011 23:47:01
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>

using namespace std;

#define maxTrie (1 << 22)
#define maxN 100005


int Trie[maxTrie], A[maxN];
int Pos[maxTrie], poz1, poz2;


inline int brother (int X)
{
	if (X % 2) return X - 1;
	return X + 1;
}


void build_trie (int X, int poz)
{
	int start;
	int bit = 20;
	
	if (X & (1 << bit)) start = 3;
	else start = 2;
	
	Trie[start] = true;
	
	-- bit;
	
	for ( ; bit >= 0; -- bit)
		if ( X & (1 << bit) )
		{
			start *= 2;
			++ start;
			Trie[start] = true;
		}
		else
		{
			start *= 2;
			Trie[start] = true;
		}
	
	Pos[X] = poz;
	
}


int search (int X)
{
	int start, nr = 0;
	int bit = 20;
	
	if (X & (1 << bit)) start = 2;
	else start = 3;
	
	if (Trie[start]) nr += (start % 2) * (1 << bit);
	else
	{
		start = brother (start);
		nr += (start % 2) * (1 << bit);
	}
	
	-- bit;
	
	for ( ; bit >= 0; -- bit)
		if ( X & (1 << bit) )
		{
			start *= 2;
			
			if (Trie[start]) nr += (start % 2) * (1 << bit);
			else
			{
				start = brother (start);
				nr += (start % 2) * (1 << bit);
			}
		}
		else
		{
			start *= 2;
			++ start;
			
			if (Trie[start]) nr += (start % 2) * (1 << bit);
			else
			{
				start = brother (start);
				nr += (start % 2) * (1 << bit);
			}
		}
	
	return nr;
	
}


int main()
{
	freopen ("xormax.in", "r", stdin);
	freopen ("xormax.out", "w", stdout);
	
	int N, sum = 0, max = 0;
	
	scanf ("%d", &N);
	
	
	build_trie (sum, 0);
	
	for (int i = 1; i <= N; ++ i)
	{
		scanf ("%d", &A[i]);
		
		sum ^= A[i];
		
		int found = search (sum);
		
		if (sum ^ found > max)
		{
			max = sum ^ found;
			poz1 = Pos[found] + 1;
			poz2 = i;
		}
		
		build_trie (sum, i);
	}
	
	
	printf ("%d %d %d", max, poz1, poz2);
	
	
	return 0;
}