Pagini recente » Cod sursa (job #211287) | Cod sursa (job #911520) | Cod sursa (job #928772) | Cod sursa (job #2272289) | Cod sursa (job #3353616)
#include <fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
const int MAX_BITS = 21;
const int MAX_NODES = 2200005;
int trie[MAX_NODES][2];
int prefix_index[MAX_NODES];
int nodeCount = 0;
void insert_trie(int value, int idx) {
int u = 0;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (value >> i) & 1;
if (trie[u][bit] == 0) {
trie[u][bit] = ++nodeCount;
}
u = trie[u][bit];
}
prefix_index[u] = idx;
}
int query_trie(int value) {
int u = 0;
for (int i = MAX_BITS; i >= 0; i--) {
int bit = (value >> i) & 1;
int opposite_bit = 1 - bit;
if (trie[u][opposite_bit] != 0) {
u = trie[u][opposite_bit];
} else {
u = trie[u][bit];
}
}
return prefix_index[u];
}
int P[100005];
int main() {
int n;
f >> n;
int max_xor = -1;
int best_start = -1, best_stop = -1;
insert_trie(0, 0);
P[0] = 0;
for (int i = 1; i <= n; i++) {
int x;
f >> x;
P[i] = P[i - 1] ^ x;
int prev_idx = query_trie(P[i]);
int current_xor = P[i] ^ P[prev_idx];
if (current_xor > max_xor) {
max_xor = current_xor;
best_start = prev_idx + 1;
best_stop = i;
}
insert_trie(P[i], i);
}
g << max_xor << " " << best_start << " " << best_stop << "\n";
return 0;
}