Pagini recente » Cod sursa (job #51880) | Cod sursa (job #1044517) | Cod sursa (job #2258774) | Cod sursa (job #1042939) | Cod sursa (job #3352600)
/*
*/
#include <fstream>
#include <vector>
const int NMAX=100'008;
class trie {
private:
struct nodd {
int st,dr;
int pos;
nodd() : st(-1), dr(-1), pos(0) {}
};
std::vector<nodd> v;
public:
trie() {
v.push_back(nodd());
}
void insert(int x,int idx) {
int nod=0;
for(int bit=20; bit>=0; bit--) {
if(x&(1<<bit)) {
if(v[nod].dr==-1) {
v.push_back(nodd());
v[nod].dr=(int)v.size()-1;
}
nod=v[nod].dr;
}
else {
if(v[nod].st==-1) {
v.push_back(nodd());
v[nod].st=(int)v.size()-1;
}
nod=v[nod].st;
}
}
v[nod].pos=idx;
}
int best(int x,int &idx) {
int ans=0;
int nod=0;
for(int bit=20; bit>=0; bit--) {
if(x&(1<<bit)) {
if(v[nod].st!=-1) {
ans|=(1<<bit);
nod=v[nod].st;
}
else {
nod=v[nod].dr;
}
}
else {
if(v[nod].dr!=-1) {
ans|=(1<<bit);
nod=v[nod].dr;
}
else {
nod=v[nod].st;
}
}
}
idx=v[nod].pos;
return ans;
}
};
int n;
int a[NMAX];
int main() {
std::ifstream fin("xormax.in");
std::ofstream fout("xormax.out");
fin >> n;
for(int i=1; i<=n; i++) {
fin >> a[i];
}
int ans=-1,st=0,dr=0;
int pref=0;
trie v;
v.insert(pref,0);
for(int i=1; i<=n; i++) {
pref^=a[i];
int pos=0;
int cand=v.best(pref,pos);
if(cand>ans) {
ans=cand;
dr=i;
st=pos+1;
}
else if(cand==ans && pos+1<st) {
ans=cand;
st=pos+1;
dr=i;
}
else if(cand==ans && pos+1==st && i-(pos+1)+1<dr-st+1) {
ans=cand;
st=pos+1;
dr=i;
}
v.insert(pref,i);
}
fout << ans << " " << st << " " << dr << "\n";
fin.close();
fout.close();
return 0;
}