Cod sursa(job #716217)

Utilizator psycho21rAbabab psycho21r Data 18 martie 2012 14:34:16
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#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);
	for(int i = 0; i < N; ++i)
		in >> a[i];
	in.close();
	trie tr;
	tr.push(a[0], 0);
	int max = 0, left = 0, right = 0;
	for(int i = 1; i < N; ++i)
	{
		a[i] ^= a[i-1];
		int j = tr.search(a[i]) - 1;
		//cout << j << " " << i << "\n";
		if(a[i]^a[j] > max)
		{
			max = a[i]^a[j];
			left = j;
			right = i;
		}
		tr.push(a[i], i + 1);
	}
	ofstream out("xormax.out");
	out << max << " " << left + 2 << " " << right + 1 << "\n";
	out.close();
	return 0;
}