Pagini recente » Cod sursa (job #2853794) | Cod sursa (job #102134) | Cod sursa (job #3354660) | Cod sursa (job #701491) | Cod sursa (job #3354718)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
struct Node {
int next[2];
int prefix_index;
};
class FlatTrie {
public:
static const int MAX_BIT = 20;
private:
vector<Node> tree;
int next_free_node;
int create_node() {
if (next_free_node >= tree.size()) {
tree.push_back({{-1, -1}, -1});
} else {
tree[next_free_node] = {{-1, -1}, -1};
}
return next_free_node++;
}
public:
FlatTrie(int estimated_size) {
tree.reserve(estimated_size);
next_free_node = 0;
create_node();
}
void insert(int val, int idx) {
int current_node = 0;
for (int bit = MAX_BIT; bit >= 0; --bit) {
int i = (val >> bit) & 1;
if (tree[current_node].next[i] == -1) {
tree[current_node].next[i] = create_node();
}
current_node = tree[current_node].next[i];
}
tree[current_node].prefix_index = idx;
}
pair<int, int> find_best(int val) const {
int current_node = 0;
int best_xor = 0;
for (int bit = MAX_BIT; bit >= 0; --bit) {
int i = (val >> bit) & 1;
int desired = 1 - i;
if (tree[current_node].next[desired] != -1) {
best_xor |= (1 << bit);
current_node = tree[current_node].next[desired];
} else {
current_node = tree[current_node].next[i];
}
}
return {best_xor, tree[current_node].prefix_index};
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n;
FlatTrie trie(n * (FlatTrie::MAX_BIT + 1) + 1);
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";
return 0;
}