Cod sursa(job #2521930)

Utilizator AlexNeaguAlexandru AlexNeagu Data 11 ianuarie 2020 18:50:42
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
struct Trie {
	Trie *bits[2];
	int key;
	Trie() {
		key = 0;
		bits[1] = NULL;
		bits[0] = NULL;
	}
};
Trie *root = new Trie();
void upd(int sum, int bit, Trie *node, int pos) {
	int upd_bit;
	if (bit == -1) {
		// cout << "\n";
		node -> key = pos;
		return;
	}
	if ((1 << bit) & sum) upd_bit = 1; else upd_bit = 0;
	// cout << upd_bit << " ";
	if (node -> bits[upd_bit] == NULL) {
		node -> bits[upd_bit] = new Trie();
	}
	upd(sum, bit - 1, node -> bits[upd_bit], pos);
}
pair < int, int > q(int bit, int sum, int ans, Trie *node) {
	if (bit == -1) {
		return make_pair(ans, node -> key);
	}
	int upd_bit;
	if ((1 << bit) & sum) upd_bit = 1; else upd_bit = 0;
	if (node -> bits[!upd_bit] != NULL) {
		return q(bit - 1, sum , ans + (1 << bit), node -> bits[!upd_bit]);
	}
	return q(bit - 1, sum, ans , node -> bits[upd_bit]);
}
int main() {
	int sum_x = 0;
	int ans[3]; ans[0] = -2e9;
	int n;
	in >> n;
	for (int i = 1; i <= n; i++) {
		int x; in >> x;
		sum_x ^= x;
		upd(sum_x, 20, root, i);
		pair < int, int > bst_res = q(20, sum_x, 0, root);
		if (ans[0] < bst_res.first) {
			ans[0] = bst_res.first;
			ans[1] = bst_res.second + 1;
			ans[2] = i;
		}
	}
	for (int i = 0; i < 3; i++) out << ans[i] << " ";
	return 0;
}