Pagini recente » Cod sursa (job #2058201) | Cod sursa (job #395074) | Cod sursa (job #1260363) | Cod sursa (job #2955269) | Cod sursa (job #1449589)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<unordered_map>
using namespace std;
typedef int var;
const var MAXBIT = 20;
struct Node {
Node *leg[2];
Node() { leg[0] = leg[1] = NULL; }
};
typedef Node* pnod;
pnod root = new Node();
unordered_map<pnod, var> Map;
var Sum[100001];
void insTree(var n, var ind) {
pnod p = root;
for(var i=MAXBIT; i>=0; i--) {
bool b = (n >> i) & 1;
if(p->leg[b] == NULL) {
p->leg[b] = new Node();
}
p = p->leg[b];
}
Map[p] = ind;
}
var xormax, start, stop;
void getMax(pnod a, pnod b) {
if(!a->leg[0] && !a->leg[1]) {
var i1 = Map[a], i2 = Map[b];
var xorr = Sum[i1] ^ Sum[i2];
if(xormax < xorr) {
xormax = xorr;
start = min(i1, i2) + 1;
stop = max(i1, i2);
}
return;
}
bool good = false;
if(a->leg[0] && b->leg[1]) {
getMax(a->leg[0], b->leg[1]);
good = true;
}
if(a->leg[1] && b->leg[0]) {
getMax(a->leg[1], b->leg[0]);
good = true;
}
if(good) return;
if(a->leg[0] && b->leg[0]) {
getMax(a->leg[0], b->leg[0]);
}
if(a->leg[1] && b->leg[1]) {
getMax(a->leg[1], b->leg[1]);
}
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
var n, sum = 0;
cin>>n;
insTree(0, 0);
for(var i=1; i<=n; i++) {
cin>>Sum[i];
Sum[i] ^= Sum[i-1];
insTree(Sum[i], i);
}
getMax(root, root);
cout<<xormax<<" "<<start<<" "<<stop;
return 0;
}