Pagini recente » Cod sursa (job #1863112) | Cod sursa (job #813973) | Cod sursa (job #105205) | Cod sursa (job #1370225) | Cod sursa (job #3144778)
#include <bits/stdc++.h>
using namespace std;
struct Trie {
Trie *Next[2];
int pos;
Trie() {
Next[0] = Next[1] = nullptr;
}
Trie(const int &value) {
pos = value;
Next[0] = Next[1] = nullptr;
}
};
Trie *root;
void Add(const int &val, const int &idx) {
Trie *node = root;
for (int i = 20; i >= 0; i--) {
bool has = (val >> i) & 1;
if (node -> Next[has] == nullptr)
node -> Next[has] = new Trie(idx);
node = node -> Next[has];
}
}
int query(const int &val) {
Trie *node = root;
for (int i = 20; i >= 0; i--) {
bool has = (val >> i) & 1;
if (node -> Next[!has])
node = node -> Next[!has];
else if (node -> Next[has])
node = node -> Next[has];
else
break;
}
return node -> pos;
}
int main() {
#ifndef TEST
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
#endif
ios_base :: sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
root = new Trie(0);
int n, x, sum = 0, start = 0, finish = 1, value = 0;
cin >> n;
vector<int> sums(n + 1);
for (int i = 1; i <= n; i++) {
cin >> x;
sum ^= x;
sums[i] = sum;
if (x > value)
value = x, start = i - 1, finish = i;
if (i > 1) {
int qry = query(sum);
if ((sum ^ sums[qry]) > value)
value = sum ^ sums[qry], start = qry, finish = i;
}
Add(sum, i);
}
cout << value << ' ' << start + 1 << ' ' << finish;
return 0;
}