Pagini recente » Cod sursa (job #2065444) | Cod sursa (job #2780849) | Cod sursa (job #2165464) | Cod sursa (job #3244009) | Cod sursa (job #1295547)
#include <fstream>
using namespace std;
// http://cs.stackexchange.com/questions/7622/finding-maximum-and-minimum-of-consecutive-xor-values
struct BinaryTrie {
struct Node {
Node* zero;
Node* one;
int pos;
Node() : Node(nullptr, nullptr, -1) {}
Node(Node* zero, Node* one, int p) : pos(p), zero(zero), one(one) {}
~Node() {
if (zero != nullptr) delete zero;
if (one != nullptr) delete one;
}
};
BinaryTrie() : Max(-1), Start(0), Stop(0) {
root = new Node;
}
~BinaryTrie() {
if (root != nullptr) delete root;
}
void add(int, int);
void search(int, int);
Node* root;
int Max;
int Start;
int Stop;
};
void BinaryTrie::add(int val, int pos)
{
Node* it = root;
for (int i = 20; i >= 0; i--) {
if (((val >> i) & 1) == 1) {
if (it->one == nullptr) {
it->one = new Node;
}
it = it->one;
}
else {
if (it->zero == nullptr) {
it->zero = new Node;
}
it = it->zero;
}
}
it->pos = pos;
}
void BinaryTrie::search(int val, int pos)
{
Node* it = root;
int solution = 0;
for (int i = 20; i >= 0; i--) {
if (((val >> i) & 1) == 1) {
if (it->zero != nullptr) {
solution ^= (1 << i);
it = it->zero;
}
else it = it->one;
}
else {
if (it->one != nullptr) {
solution ^= (1 << i);
it = it->one;
}
else it = it->zero;
}
}
if (solution > Max) {
Max = solution;
Start = it->pos;
Stop = pos;
}
}
int main()
{
ifstream in("xormax.in");
ofstream out("xormax.out");
int N, x, z = 0;
BinaryTrie* bt = new BinaryTrie;
in >> N;
bt->add(0, 1);
for (int i = 1; i <= N; i++) {
in >> x;
z ^= x;
bt->search(z, i);
bt->add(z, i + 1);
}
out << bt->Max << ' ' << bt->Start << ' ' << bt->Stop;
in.close();
out.close();
delete bt;
return 0;
}