Pagini recente » Cod sursa (job #3319105) | Cod sursa (job #1466771) | Cod sursa (job #3251282) | Cod sursa (job #991914) | Cod sursa (job #3310851)
#include <fstream>
#include <vector>
#include <climits> // INT_MIN
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct TrieNode {
TrieNode* child[2] = {nullptr, nullptr};
int index = -1; // indexul prefixului
};
void insert(TrieNode* root, int num, int idx) {
TrieNode* node = root;
for (int i = 30; i >= 0; --i) {
int bit = (num >> i) & 1;
if (!node -> child[bit]) {
node -> child[bit] = new TrieNode();
}
node = node -> child[bit];
}
node -> index = idx;
}
pair<int,int> query(TrieNode* root, int num) {
TrieNode* node = root;
int res = 0;
for (int i = 30; i >= 0; --i) {
int bit = (num >> i) & 1;
int preferred = 1 - bit;
if (node -> child[preferred]) {
res |= (1 << i);
node = node -> child[preferred];
} else {
node = node -> child[bit];
}
}
return {res, node -> index};
}
int main() {
int N;
fin >> N;
vector<int> a(N);
for(int i = 0; i < N; ++i) {
fin >> a[i];
}
fin.close();
vector<int> prefix(N + 1, 0);
for (int i = 1; i <= N; ++i) {
prefix[i] = prefix[i - 1] ^ a[i - 1];
}
TrieNode* root = new TrieNode();
insert(root, 0, 0);
int max_xor = INT_MIN;
int start = 1, stop = 1;
for (int r = 1; r <= N; ++r) {
auto [val, l_idx] = query(root, prefix[r]);
if (val > max_xor || (val == max_xor && r < stop) || (val == max_xor && r == stop && l_idx + 1 > start)) {
max_xor = val;
start = l_idx + 1;
stop = r;
}
insert(root, prefix[r], r);
}
fout << max_xor << " " << start << " " << stop << "\n";
return 0;
}