Cod sursa(job #2521981)

Utilizator AlexNeaguAlexandru AlexNeagu Data 11 ianuarie 2020 19:30:02
Problema Xor Max Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 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;
	}
}
if (ans[1] > ans[2]) ans[1] = ans[2];
for (int i = 0; i < 3; i++) out << ans[i] << " ";
return 0;
}