Pagini recente » Cod sursa (job #2704528) | Cod sursa (job #92911) | Cod sursa (job #92733) | Cod sursa (job #2615262) | Cod sursa (job #2660742)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
class Trie {
public:
Trie(int _val) : val(_val) {
children[0] = children[1] = nullptr;
}
void add(const char* pos, const int& val) {
if (*pos == '\0') {
this->val = val;
return;
}
if (!children[*pos - '0']) {
children[*pos - '0'] = new Trie(0);
}
children[*pos - '0']->add(pos + 1, val);
}
Trie* findClose(const char* pos) {
if (*pos == '\0') {
return this;
}
if (children[*pos - '0']) {
return children[*pos - '0']->findClose(pos + 1);
}
if (children[1 - (*pos - '0')]) {
return children[1 - (*pos - '0')]->findClose(pos + 1);
}
return nullptr;
}
inline int getVal() { return val; }
private:
int val;
Trie* children[2];
};
Trie* xorTrie = new Trie(0);
int xorp[100005];
string numToBinaryString(int num) {
string s;
for (int bit = 22; bit >= 0; bit--)
s += '0' + (!!(num & (1 << bit)));
return s;
}
int main() {
int n;
in >> n;
xorTrie->add("00000000000000000000000", 0);
int maxx = 0, l = 0, r = 0;
for (int i = 1; i <= n; i++) {
int x;
in >> x;
xorp[i] = xorp[i - 1] ^ x;
string invXorStr = numToBinaryString(~xorp[i]);
Trie* best = xorTrie->findClose(invXorStr.c_str());
if ((xorp[i] ^ xorp[best->getVal()]) > maxx) {
maxx = xorp[i] ^ xorp[best->getVal()];
l = best->getVal() + 1;
r = i;
}
string xorStr = numToBinaryString(xorp[i]);
xorTrie->add(xorStr.c_str(), i);
}
out << maxx << ' ' << l << ' ' << r;
}