Pagini recente » Cod sursa (job #2674110) | Cod sursa (job #3275694) | Cod sursa (job #2542739) | Cod sursa (job #2658606) | Cod sursa (job #3234216)
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
int n, res, start, stop;
struct Trie {
Trie* son[2];
int pos;
Trie() {
son[0] = son[1] = nullptr;
pos = 0;
}
};
Trie* root = new Trie();
void insert(Trie* node, int val, int bitPos, int vecPos) {
if (bitPos == -1) {
node->pos = vecPos;
return;
}
int bit = (val & (1 << bitPos)) > 0;
if (node->son[bit] == nullptr) {
node->son[bit] = new Trie();
}
insert(node->son[bit], val, bitPos - 1, vecPos);
}
pair<int, int> query(Trie* node, int val, int bitPos) {
if (bitPos == -1) {
return make_pair(0, node->pos);
}
int bit = (val & (1 << bitPos)) > 0;
pair<int, int> res;
if (node->son[bit ^ 1] != nullptr) {
res = query(node->son[bit ^ 1], val, bitPos - 1);
res.first += (1 << bitPos);
} else {
res = query(node->son[bit], val, bitPos - 1);
}
return res;
}
int main() {
ifstream in("xormax.in");
ofstream out("xormax.out");
insert(root, 0, 20, 0);
int sumXor = 0;
in >> n;
for (int i = 1; i <= n; i++) {
int val;
in >> val;
sumXor ^= val;
auto crtRes = query(root, sumXor, 20);
if (crtRes.first > res) {
res = crtRes.first;
start = crtRes.second + 1;
stop = i;
}
insert(root, sumXor, 20, i);
}
out << res << " " << start << " " << stop << "\n";
return 0;
}