Pagini recente » Cod sursa (job #2521872) | Istoria paginii runda/sim10_2 | Cod sursa (job #113866) | Cod sursa (job #131025) | Cod sursa (job #2521947)
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int mx = - 1000000000;
int start = 0, finish = 0;
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 + 1);
}
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 n;
in >> n;
for (int i = 1; i <= n; i++) {
int x; in >> x;
sum_x ^= x;
upd(sum_x, 22, root, i);
pair < int, int > bst_res = q(22, sum_x, 0, root);
if (mx < bst_res.first) {
mx = bst_res.first;
start = bst_res.second;
finish = i;
}
}
out << mx << " " << start << " " << finish << "\n";
return 0;
}