Pagini recente » Cod sursa (job #3351762) | Cod sursa (job #2026495) | Cod sursa (job #1003943) | Cod sursa (job #2296452) | Cod sursa (job #3330114)
#include <fstream>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
class Trie {
private:
struct node {
node *sons[2];
int lastPos = 0;
node() {
sons[0] = sons[1] = NULL;
}
} *root = new node;
void addxxor(node *n, int xxor, int bit, int pos) {
if (bit == -1) {
n->lastPos = pos;
return;
}
bool valBit = ((xxor & (1 << bit)) != 0);
if (!n->sons[valBit]) {
n->sons[valBit] = new node;
}
addxxor(n->sons[valBit], xxor, bit - 1, pos);
}
pair<int, int> getxxorMax(node *n, int xxor, int bit) {
if (bit == -1) {
return make_pair(0, n->lastPos);
}
bool valWantedBit = ((xxor & (1 << bit)) == 0);
if (n->sons[valWantedBit]) {
pair<int, int> ans = getxxorMax(n->sons[valWantedBit], xxor, bit - 1);
ans.first += (1 << bit);
return ans;
}
valWantedBit = 1 - valWantedBit;
if (n->sons[valWantedBit]) {
return getxxorMax(n->sons[valWantedBit], xxor, bit - 1);
}
return make_pair(0, 0);
}
public:
Trie() {
}
void add(int nr, int pos) {
addxxor(root, nr, 21, pos);
}
pair<int, int> get(int nr) {
return getxxorMax(root, nr, 21);
}
};
int main() {
int n; cin >> n;
Trie trie;
int prefixXor = 0, ans = -1, st = 0, dr = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
prefixXor ^= x;
pair<int, int> pls = trie.get(prefixXor);
if (pls.first > ans) {
ans = pls.first;
st = pls.second;
dr = i;
}
trie.add(prefixXor, i);
}
cout << ans << ' ' << st + 1 << ' ' << dr << '\n';
}