Pagini recente » Monitorul de evaluare | Cod sursa (job #1102996) | Cod sursa (job #3229285) | Cod sursa (job #3249941) | Cod sursa (job #3355902)
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
struct Element {
int val;
int prefix_xor;
int idx;
};
struct TrieNode {
TrieNode* children[2] = {nullptr, nullptr};
int idx = -1;
};
void insert(TrieNode* root, int val, int idx) {
TrieNode* curr = root;
for (int i = 30; i >= 0; i--) {
int bit = (val >> i) & 1;
if (!curr->children[bit]) {
curr->children[bit] = new TrieNode();
}
curr = curr->children[bit];
}
curr->idx = idx;
}
pair<int, int> query(TrieNode* root, int val) {
TrieNode* curr = root;
int max_xor = 0;
for (int i = 30; i >= 0; i--) {
int bit = (val >> i) & 1;
int flipped = 1 - bit;
if (curr->children[flipped]) {
max_xor |= (1 << i);
curr = curr->children[flipped];
} else if (curr->children[bit]) {
curr = curr->children[bit];
} else {
return {-1, -1};
}
}
return {max_xor, curr->idx};
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int n;
if (!(cin >> n)) return 0;
vector<Element> arr(n);
int current_prefix = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i].val;
current_prefix ^= arr[i].val;
arr[i].prefix_xor = current_prefix;
arr[i].idx = i + 1;
}
TrieNode* root = new TrieNode();
insert(root, 0, 0);
int best_max_xor = -1;
int best_start = 0;
int best_end = 0;
for (int i = 0; i < n; i++) {
pair<int, int> result = query(root, arr[i].prefix_xor);
if (result.first > best_max_xor) {
best_max_xor = result.first;
best_start = result.second + 1;
best_end = arr[i].idx;
}
insert(root, arr[i].prefix_xor, arr[i].idx);
}
cout << best_max_xor << " " << best_start << " " << best_end << "\n";
return 0;
}