Pagini recente » Cod sursa (job #1772644) | Cod sursa (job #902068) | Grigore Moisil 2017 Clasa a 10-a | Cod sursa (job #232746) | Cod sursa (job #2660740)
#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];
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;
char invXorString[25];
for (int bit = 20; bit >= 0; bit--)
invXorString[20 - bit] = '0' + (!(xorp[i] & (1 << bit)));
invXorString[21] = '\0';
Trie* best = xorTrie->findClose(invXorString);
if ((xorp[i] ^ xorp[best->getVal()]) > maxx) {
maxx = xorp[i] ^ xorp[best->getVal()];
l = best->getVal() + 1;
r = i;
}
char xorString[25];
for (int bit = 20; bit >= 0; bit--)
xorString[20 - bit] = '0' + (!!(xorp[i] & (1 << bit)));
xorString[21] = '\0';
xorTrie->add(xorString, i);
}
out << maxx << ' ' << l << ' ' << r;
}