Cod sursa(job #716546)

Utilizator psycho21rAbabab psycho21r Data 18 martie 2012 22:57:08
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
//Ciuperci
#include <iostream>
#include <fstream>
#include <vector>
#define BIT_LIM 22
using namespace std;
class trie
{
	struct node
	{
		int ind;
		node *left, *right;
		node()
		{
			ind = 0;
			left = right = NULL;
		}
	};
	node *root;
	public:
		trie()
		{
			root = new node;
		}
		void push(int x, int ind)
		{
			node *here = root;
			for(int i = BIT_LIM; i >= 0; --i)
			{
				if(x & (1 << i))
				{
					if(here -> right == NULL)
						here -> right = new node;
					here = here -> right;
				}
				else
				{
					if(here -> left == NULL)
						here -> left = new node;
					here = here -> left;
				}
			}
			here -> ind = ind;
		}
		int search(int x)
		{
			node *here = root;
			for(int i = BIT_LIM; i >= 0; --i)
			{
				if(x & (1 << i))
				{
					if(here -> left != NULL)
						here = here -> left;
					else
						here = here -> right;
				}
				else
				{
					if(here -> right != NULL)
						here = here -> right;
					else
						here = here -> left;
				}
			}
			return here -> ind;
		}
		
};

int main()
{
	int N;
	ifstream in("xormax.in");
	in >> N;
	vector<int> a(N+1), sum(N+1);	
	int max = -1, left, right;
	trie tr;
	tr.push(0, 0);
	a[0] = 0;
	for(int i = 1; i <= N; ++i)
	{
		in >> a[i];	
		sum[i] = sum[i-1] ^ a[i];
		int j = tr.search(sum[i]);
		if((sum[j]^sum[i]) > max)
		{
			max = sum[j]^sum[i];
			left = j;
			right = i;
		}
		tr.push(sum[i], i);
	}
	ofstream out("xormax.out");
	out << max << " " << left + 1 << " " << right << "\n";
	out.close();
	return 0;
}