Pagini recente » Cod sursa (job #1098451) | Cod sursa (job #3337723) | Cod sursa (job #1406322) | Cod sursa (job #2492032) | Cod sursa (job #3354337)
#include <iostream>
#include <fstream>
#include <vector>
std::ifstream fin("xormax.in");
std::ofstream fout("xormax.out");
struct Node {
Node* copii[2];
int index;
Node() {
copii[0] = nullptr;
copii[1] = nullptr;
index = -1;
}
~Node() {
delete copii[0];
delete copii[1];
}
};
class Trie {
Node* root;
public:
Trie() {
root = new Node();
}
~Trie() {
delete root;
}
void insert(int numar, int index) {
Node* curr = root;
for (int i = 20; i >= 0; i--) {
int bit = (numar >> i) & 1;
if (curr->copii[bit] == nullptr) {
curr->copii[bit] = new Node();
}
curr = curr->copii[bit];
}
curr->index = index;
}
std::pair<int, int> findMax(int numar) {
Node* curr = root;
int value = 0;
for (int i = 20; i >= 0; i--) {
int bit = (numar >> i) & 1;
if (curr->copii[bit ^ 1] != nullptr) {
curr = curr->copii[bit ^ 1];
value = value * 2 + (bit ^ 1);
}
else {
curr = curr->copii[bit];
value = value * 2 + bit;
}
}
return std::make_pair(value, curr->index);
}
};
int n;
int a[100005], aux[100005];
int main() {
Trie trie;
int m, l, r, x, y;
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> a[i];
}
aux[0] = m = 0;
trie.insert(aux[0], 0);
for (int i = 1; i <= n; i++) {
aux[i] = aux[i - 1] ^ a[i];
auto[x, y] = trie.findMax(aux[i]);
if ((x ^ aux[i]) >= m) {
m = x ^ aux[i];
l = y; r = i;
}
trie.insert(aux[i], i);
}
fout << m << " " << l + 1 << " " << r << "\n";
return 0;
}