Pagini recente » Cod sursa (job #2458554) | Cod sursa (job #771126) | Cod sursa (job #773184) | Cod sursa (job #240135) | Cod sursa (job #2521930)
#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;
}