Pagini recente » Cod sursa (job #1210398) | Cod sursa (job #3320038) | Cod sursa (job #144508) | Cod sursa (job #1064557) | Cod sursa (job #3354453)
#include <iostream>
#include <cassert>
#include <memory>
#include <vector>
#include <fstream>
using namespace std;
class Trie {
public:
static const int MAX_BIT = 20;
protected:
class Node {
protected:
int value;
int prefix_index;
vector<shared_ptr<Node>> next;
public:
Node(int value) :
value(value),
prefix_index(-1),
next(2, nullptr) {}
void set_prefix_index(int idx) {
prefix_index = idx;
}
int get_prefix_index() const {
return prefix_index;
}
shared_ptr<Node> get_node(size_t i) const {
return next[i];
}
void add_node(size_t i, int val) {
next[i] = make_shared<Node>(val);
}
};
shared_ptr<Node> root;
public:
Trie() : root(make_shared<Node>(-1)) {}
void insert(int val, int idx) {
shared_ptr<Node> parser = root;
for (int bit = MAX_BIT; bit >= 0; --bit) {
size_t i = (val >> bit) & 1;
if (!parser->get_node(i))
parser->add_node(i, i);
parser = parser->get_node(i);
}
parser->set_prefix_index(idx);
}
pair<int, int> find_best(int val) {
shared_ptr<Node> parser = root;
int best_xor = 0;
for (int bit = MAX_BIT; bit >= 0; --bit) {
size_t i = (val >> bit) & 1;
// vrem opusul
size_t desired = 1 - i;
if (parser->get_node(desired)) {
best_xor |= (1 << bit);
parser = parser->get_node(desired);
} else {
parser = parser->get_node(i);
}
}
return {best_xor, parser->get_prefix_index()};
}
};
int main() {
ifstream fin("xormax.in");
if (!fin.is_open()) {
cerr << "xormax.in failed to open!" << endl;
return 1;
}
ofstream fout("xormax.out");
if (!fout.is_open()) {
cerr << "xormax.out failed to open!" << endl;
return 2;
}
int n;
if (!(fin >> n)) {
return 0;
}
Trie trie;
trie.insert(0, 0);
int current_prefix = 0;
int max_xor = -1;
int start_pos = -1;
int end_pos = -1;
for (int j = 1; j <= n; ++j) {
int val;
fin >> val;
current_prefix ^= val;
auto [best_xor, best_index] = trie.find_best(current_prefix);
if (best_xor > max_xor) {
max_xor = best_xor;
start_pos = best_index + 1;
end_pos = j;
}
trie.insert(current_prefix, j);
}
fout << max_xor << " " << start_pos << " " << end_pos << "\n";
fin.close();
fout.close();
return 0;
}