Pagini recente » Cod sursa (job #1769778) | Cod sursa (job #2555693) | Cod sursa (job #1555894) | Cod sursa (job #2170753) | Cod sursa (job #1449602)
#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();
vector<var> Ap[100001];
var Sum[100001];
unordered_map<var, var> Ind;
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;
var ind = 0;
vector<var> Pret;
bool Taken[1<<21];
void updateEnd(var a, var b) {
vector<var> &V = Ap[Ind[b]];
auto it = upper_bound(V.begin(), V.end(), Ap[Ind[a]][0]);
if(it == V.end()) return;
stop = min(stop, *it);
}
void getEnd() {
for(auto p : Pret) {
updateEnd(xormax ^ p, p);
}
}
void getMax(pnod a, pnod b, var ai, var bi) {
if(!a->leg[0] && !a->leg[1]) {
if( xormax < (ai ^ bi) ) {
xormax = ai ^ bi;
while(!Pret.empty()) {
Taken[Pret.back()] = 0;
Pret.pop_back();
}
}
if( xormax == (ai ^ bi) ) {
if(!Taken[ai]) Taken[ai] = 1, Pret.push_back(ai);
if(!Taken[bi]) Taken[bi] = 1, Pret.push_back(bi);
}
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);
Ind[0] = 0;
Ap[0].push_back(0);
for(var i=1; i<=n; i++) {
cin>>Sum[i];
Sum[i] ^= Sum[i-1];
if(Ind.find(Sum[i]) == Ind.end()) {
Ind[Sum[i]] = ++ind;
}
Ap[Ind[Sum[i]]].push_back(i);
insTree(Sum[i], i);
}
getMax(root, root, 0, 0);
getEnd();
for(var i=stop-1; ;i--) {
if(Sum[i] == (xormax ^ Sum[stop])) {
cout<<xormax<<" "<<i+1<<" "<<stop;
return 0;
}
}
return 0;
}