Pagini recente » Cod sursa (job #849567) | Cod sursa (job #373143) | Cod sursa (job #2343433) | Cod sursa (job #619326) | Cod sursa (job #904877)
Cod sursa(job #904877)
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define FIO
#ifdef FIO
ifstream in("xormax.in");
ofstream out("xormax.out");
#else
#define in cin
#define out cout
#endif
const int MAX_N = 100100;
const int MAX_LOG = 30;
int N;
int v[MAX_N];
class Trie {
public:
Trie();
void add_entry(int num, int index);
pair<int, int> find_not(int num);
private:
int get_node(int, bool);
void set_node(int, bool, int);
struct TrieNode {
TrieNode();
int index;
int next[2];
};
vector<TrieNode> trie;
};
int main() {
in >> N;
Trie t;
int xor_sum = 0;
in >> xor_sum;
t.add_entry(xor_sum, 1);
int xor_max = xor_sum, a = 1, b = 1;
for (int i = 2, x; i <= N; ++i) {
in >> x;
xor_sum ^= x;
pair<int, int> p = t.find_not(xor_sum);
if (xor_sum ^ p.first > xor_max) {
xor_max = xor_sum ^ p.first;
a = p.second + 1;
b = i;
}
t.add_entry(xor_sum, i);
}
out << xor_max << ' ' << a << ' ' << b;
return 0;
}
void Trie::add_entry(int num, int index) {
int current_node = 0;
for (int l = MAX_LOG; l >= 0; --l) {
bool take_bit = num & (1 << l) ? 1 : 0;
int next_node = get_node(current_node, take_bit);
if (next_node == -1) {
set_node(current_node, take_bit, trie.size());
current_node = trie.size();
trie.push_back(TrieNode());
} else {
current_node = next_node;
}
}
trie[current_node].index = index;
}
pair<int, int> Trie::find_not(int num) {
int result = 0, current_node = 0;
for (int l = MAX_LOG; l >= 0; --l) {
bool take_bit = (num & (1 << l)) ? 0 : 1;
int next_node = get_node(current_node, take_bit);
if (next_node == -1) {
take_bit ^= 1;
next_node = get_node(current_node, take_bit);
}
result ^= take_bit ? (1 << l) : 0;
current_node = next_node;
}
return make_pair(result, trie[current_node].index);
}
inline int Trie::get_node(int source, bool bit) {
return trie[source].next[bit];
}
inline void Trie::set_node(int source, bool bit, int position) {
trie[source].next[bit] = position;
}
Trie::Trie() {
trie.push_back(TrieNode());
}
Trie::TrieNode::TrieNode() {
index = next[0] = next[1] = -1;
}