Pagini recente » Cod sursa (job #852140) | Cod sursa (job #1998475) | Cod sursa (job #3245260) | Cod sursa (job #2908830) | Cod sursa (job #2507330)
#include <bits/stdc++.h>
const int MAX_N = 100005;
const int BITS = 24;
int n;
int arr[MAX_N];
int xor_sums[MAX_N];
struct Trie {
int value;
Trie *child[2];
Trie() {
child[0] = child[1] = NULL;
}
};
void insert(Trie *root, int bit, int value) {
if (bit == - 1) {
root->value = value;
} else {
if (root->child[((1 << bit) & value) > 0] == NULL) {
root->child[((1 << bit) & value) > 0] = new Trie;
}
insert(root->child[((1 << bit) & value) > 0], bit - 1, value);
}
}
int query(Trie *root, int bit, int value) {
if (bit == - 1) {
return (root->value ^ value);
} else {
if (((1 << bit) & value) > 0) {
if (root->child[0] == NULL) {
return query(root->child[1], bit - 1, value);
} else {
return query(root->child[0], bit - 1, value);
}
} else {
if (root->child[1] == NULL) {
return query(root->child[0], bit - 1, value);
} else {
return query(root->child[1], bit - 1, value);
}
}
}
}
int main() {
int ans, max, lo, ri;
Trie *root = new Trie;
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
std::cin >> n;
max = - 1;
for (int i = 1; i <= n; ++i) {
scanf("%d", &arr[i]);
xor_sums[i] = xor_sums[i - 1] ^ arr[i];
insert(root, BITS, xor_sums[i]);
ans = query(root, BITS, xor_sums[i]);
if (ans > max) {
max = ans;
ri = i;
}
}
lo = ri;
while ((xor_sums[ri] ^ xor_sums[lo - 1]) != max) {
--lo;
}
std::cout << max << " " << lo << " " << ri << "\n";
return 0;
}