Cod sursa(job #1295547)

Utilizator vgabi94Vaduva Gabriel vgabi94 Data 19 decembrie 2014 19:17:54
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
using namespace std;

// http://cs.stackexchange.com/questions/7622/finding-maximum-and-minimum-of-consecutive-xor-values 

struct BinaryTrie {
	struct Node {
		Node* zero;
		Node* one;
		int pos;

		Node() : Node(nullptr, nullptr, -1) {}
		Node(Node* zero, Node* one, int p) : pos(p), zero(zero), one(one) {}
		~Node() {
			if (zero != nullptr) delete zero;
			if (one != nullptr) delete one;
		}
	};

	BinaryTrie() : Max(-1), Start(0), Stop(0) {
		root = new Node;
	}
	~BinaryTrie() {
		if (root != nullptr) delete root;
	}

	void add(int, int);
	void search(int, int);
	Node* root;
	int Max;
	int Start;
	int Stop;
};

void BinaryTrie::add(int val, int pos)
{
	Node* it = root;
	for (int i = 20; i >= 0; i--) {
		if (((val >> i) & 1) == 1) {
			if (it->one == nullptr) {
				it->one = new Node;
			}
			it = it->one;
		}
		else {
			if (it->zero == nullptr) {
				it->zero = new Node;
			}
			it = it->zero;
		}
	}
	it->pos = pos;
}

void BinaryTrie::search(int val, int pos)
{
	Node* it = root;
	int solution = 0;
	
	for (int i = 20; i >= 0; i--) {
		if (((val >> i) & 1) == 1) {
			if (it->zero != nullptr) {
				solution ^= (1 << i);
				it = it->zero;
			}
			else it = it->one;
		}
		else {
			if (it->one != nullptr) {
				solution ^= (1 << i);
				it = it->one;
			}
			else it = it->zero;
		}
	}

	if (solution > Max) {
		Max = solution;
		Start = it->pos;
		Stop = pos;
	}
}

int main()
{
	ifstream in("xormax.in");
	ofstream out("xormax.out");
	int N, x, z = 0; 
	BinaryTrie* bt = new BinaryTrie;
	in >> N;

	bt->add(0, 1);
	for (int i = 1; i <= N; i++) {
		in >> x;
		z ^= x;
		bt->search(z, i);
		bt->add(z, i + 1);
	}

	out << bt->Max << ' ' << bt->Start << ' ' << bt->Stop;

	in.close();
	out.close();
	delete bt;
	return 0;
}