Pagini recente » Cod sursa (job #1660569) | Cod sursa (job #675062) | Cod sursa (job #1324989) | Cod sursa (job #1375907) | Cod sursa (job #1449594)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<unordered_map>
using namespace std;
typedef int var;
const var MAXBIT = 20;
const var ADD = (1 << 21);
bool Gets[ADD << 1];
unordered_map<var, var> Map;
var Sum[100001];
void insTree(var n, var ind) {
var node = 1;
for(var i=MAXBIT; i>=0; i--) {
bool b = (n >> i) & 1;
Gets[node*2+b] = 1;
node = node*2 + b;
}
}
var xormax, start, stop = 200000;
var n;
vector< pair<var, var> >Sols;
void getMax(var a, var b) {
if(a >= ADD) {
var rez = (a-ADD) ^ (b-ADD);
if(xormax < rez) {
xormax = rez;
Sols.clear();
}
if(xormax == rez) {
Sols.push_back(make_pair(a-ADD, b-ADD));
}
return;
}
bool good = false;
if(Gets[2*a] && Gets[2*b+1])
getMax(2*a, 2*b+1), good=true;
if(Gets[2*a+1] && Gets[2*b])
getMax(2*a+1, 2*b), good=true;
if(good) return;
if(Gets[2*a] && Gets[2*b])
getMax(2*a, 2*b);
if(Gets[2*a+1] && Gets[2*b+1])
getMax(2*a+1, 2*b+1);
}
void getLims(var a, var b) {
var i;
for(i=0; i<=n && Sum[i] != a; i++);
var be = i;
for(;i<=n && Sum[i] != b; i++) {
if(Sum[i] == a)
be = i;
}
var en = i;
if(stop > en) {
start = be;
stop = en;
}
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
var sum = 0;
cin>>n;
insTree(0, 0);
for(var i=1; i<=n; i++) {
cin>>Sum[i];
Sum[i] ^= Sum[i-1];
Map[Sum[i]] = i;
insTree(Sum[i], i);
}
getMax(1, 1);
for(auto p: Sols) {
getLims(p.first, p.second);
getLims(p.second, p.first);
}
cout<<xormax<<" "<<start+1<<" "<<stop;
return 0;
}