Pagini recente » Cod sursa (job #163002) | Cod sursa (job #951615) | Cod sursa (job #1286065) | Cod sursa (job #921872) | Cod sursa (job #2246120)
// 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;
}