Pagini recente » Cod sursa (job #1004388) | Cod sursa (job #36065) | Cod sursa (job #70398) | Cod sursa (job #1113753) | Cod sursa (job #2702818)
// Editorialul la această problemă se va găsi la:
// https://infogenius.ro/trie-aplicatii/#problema-xor-max-de-pe-infoarena-11
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
class Trie {
private:
struct Node {
int pos = 0;
int next[2] = {};
};
vector<Node> trie{1};
public:
void insert(int pos, int val) {
int node = 0;
for (int bit = 20; bit >= 0; bit--) {
bool now = (val & (1 << bit));
if (!trie[node].next[now]) {
trie[node].next[now] = trie.size();
trie.emplace_back();
}
node = trie[node].next[now];
}
trie[node].pos = pos;
}
tuple<int, int, int> query(int pos, int val) {
int node = 0, ans = 0;
for (int bit = 20; bit >= 0; bit--) {
bool now = (val & (1 << bit));
if (!trie[node].next[!now])
node = trie[node].next[now];
else {
node = trie[node].next[!now];
ans |= (1 << bit);
}
}
return make_tuple(ans, -pos, trie[node].pos + 1);
}
};
int main() {
Trie trie; trie.insert(0, 0);
int n; fin >> n;
tuple<int, int, int> ans(-1, 0, 0);
for (int i = 1, sum = 0; i <= n; i++) {
int x; fin >> x; sum ^= x;
ans = max(ans, trie.query(i, sum));
trie.insert(i, sum);
}
fout << get<0>(ans) << ' ' << get<2>(ans) << ' ' << -get<1>(ans) << '\n';
return 0;
}