Cod sursa(job #2246120)

Utilizator cautionPopescu Teodor caution Data 26 septembrie 2018 18:18:30
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
// 26-09-2018
// https://www.infoarena.ro/problema/xormax
// binary tree + query with xor

#include <bits/stdc++.h>

using namespace std;

class BinaryNode {
public:
	BinaryNode *zero, *one;
	unsigned int value;
	int info;
	BinaryNode(unsigned int value, int info) {
		this->zero = NULL;
		this->one = NULL;
		this->value = value;
		this->info = info;
	}
};

class BinaryTrie {
	BinaryNode *root;
	int max_depth;
public:
	BinaryTrie(int max_depth) {
		this->root = new BinaryNode(0, 0);
		this->max_depth = max_depth;
	}

	void add(unsigned int x, int info) {
		BinaryNode *p = root;
		for (int i = max_depth - 1; i >= 0; --i) {
			int bit = (x >> i) % 2;
			if (bit == 0) {
				if (p->zero == NULL) p->zero = new BinaryNode(x, info);
				p = p->zero;
			} else {
				if (p->one == NULL) p->one = new BinaryNode(x, info);
				p = p->one;
			}
		}
		p->value = x;
		p->info = info;
	}

	// Retrieve the number the number in trie, let that be 'a', for which
	// a ^ x is as big as possible
	BinaryNode *getClosestComplementary(unsigned int x) {
		BinaryNode *p = root;
		for (int i = max_depth - 1; i >= 0; --i) {
			int bit = (x >> i) % 2;
			if (p->zero == NULL && p->one == NULL) return p;
			if (bit == 1) {
				if (p->zero == NULL) p = p->one;
				else p = p->zero;
			} else {
				if (p->one == NULL) p = p->zero;
				else p = p->one;
			}
		}
		return p;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	freopen("xormax.in", "rt", stdin);
	freopen("xormax.out", "wt", stdout);
	int n, s = 0, ans = 0, l = 0, r = 0;
	// The trie's nodes will hold the index of the last element in the xor sum
	// as additional information
	BinaryTrie trie(22);
	trie.add(0, 0);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x;
		cin >> x;
		s ^= x;
		BinaryNode *p = trie.getClosestComplementary(s);
		int current_max = p->value ^ s;
		if (current_max > ans) {
			ans = current_max;
			l = p->info + 1;
			r = i;
		}
		trie.add(s, i);
	}
	cout << ans << ' ' << l << ' ' << r << '\n';
	
	return 0;
}