Cod sursa(job #716522)

Utilizator psycho21rAbabab psycho21r Data 18 martie 2012 22:12:32
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
//Ciuperci
#include <iostream>
#include <fstream>
#include <vector>
#define BIT_LIM 22
using namespace std;
class trie
{
	struct node
	{
		int ind, info;
		node *left, *right;
		node()
		{
			ind = info = 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;
			here -> info = x;
		}
		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;
				}
			}
			int bit = x ^ here -> info;
			return here -> ind;
		}
		
};

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