Pagini recente » Cod sursa (job #2916069) | Cod sursa (job #1326157) | Cod sursa (job #502778) | Cod sursa (job #2266541) | Cod sursa (job #1449599)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<unordered_map>
#include<vector>
#include<algorithm>
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< var, vector<var> > Ap;
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];
}
}
var xormax, start, stop = 200000;
void updateEnd(var a, var b) {
vector<var> &V = Ap[b];
auto it = upper_bound(V.begin(), V.end(), Ap[a][0]);
if(it == V.end()) return;
stop = min(stop, *it);
}
void getMax(pnod a, pnod b, var ai, var bi) {
if(!a->leg[0] && !a->leg[1]) {
if( xormax < (ai ^ bi) ) {
xormax = ai ^ bi;
}
if( xormax == (ai ^ bi) ) {
updateEnd(ai, bi);
updateEnd(bi, ai);
}
return;
}
bool good = false;
if(a->leg[0] && b->leg[1]) {
getMax(a->leg[0], b->leg[1], ai<<1, bi<<1|1);
good = true;
}
if(a->leg[1] && b->leg[0]) {
getMax(a->leg[1], b->leg[0], ai<<1|1, bi<<1);
good = true;
}
if(good) return;
if(a->leg[0] && b->leg[0]) {
getMax(a->leg[0], b->leg[0], ai<<1, bi<<1);
}
if(a->leg[1] && b->leg[1]) {
getMax(a->leg[1], b->leg[1], ai<<1|1, bi<<1|1);
}
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
var n, sum = 0;
cin>>n;
insTree(0, 0);
Ap[0].push_back(0);
for(var i=1; i<=n; i++) {
cin>>Sum[i];
Sum[i] ^= Sum[i-1];
Ap[Sum[i]].push_back(i);
insTree(Sum[i], i);
}
getMax(root, root, 0, 0);
for(var i=stop-1; ;i--) {
if(Sum[i] == (xormax ^ Sum[stop])) {
cout<<xormax<<" "<<i+1<<" "<<stop;
return 0;
}
}
return 0;
}