Pagini recente » Cod sursa (job #184871) | Cod sursa (job #1351468) | Cod sursa (job #2633666) | Cod sursa (job #2032943) | Cod sursa (job #3172372)
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
using namespace std;
const int BITS = 21;
struct TrieNode {
TrieNode *children[2];
int index;
TrieNode() {
children[0] = children[1] = nullptr;
index = -1;
}
};
void insert(TrieNode *root, int num, int index) {
TrieNode *node = root;
for (int i = BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
if (!node->children[bit]) {
node->children[bit] = new TrieNode();
}
node = node->children[bit];
}
node->index = index;
}
pair<int, int> maxXorWithIndex(TrieNode *root, int num) {
TrieNode *node = root;
int maxXor = 0;
for (int i = BITS; i >= 0; i--) {
int bit = (num >> i) & 1;
int oppositeBit = bit ^ 1;
if (node->children[oppositeBit]) {
maxXor |= (1 << i);
node = node->children[oppositeBit];
} else {
node = node->children[bit];
}
}
return make_pair(maxXor, node->index);
}
int main() {
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
TrieNode *root = new TrieNode();
insert(root, 0, -1);
int maxXor = 0, maxXorStart = 0, maxXorEnd = 0, prefixXor = 0;
for (int i = 0; i < n; i++) {
prefixXor ^= arr[i];
pair<int, int> result = maxXorWithIndex(root, prefixXor);
if (result.first > maxXor) {
maxXor = result.first;
maxXorStart = result.second + 1;
maxXorEnd = i;
}
insert(root, prefixXor, i);
}
cout << maxXor << " " << maxXorStart + 1 << " " << maxXorEnd + 1 << endl;
return 0;
}