Pagini recente » Cod sursa (job #2989208) | Cod sursa (job #1219075) | Cod sursa (job #2487699) | Istoria paginii runda/3333333333333 | Cod sursa (job #2470001)
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
ifstream fi("xormax.in");
ofstream fo("xormax.out");
const int NMAX=1e5+5;
int n,s[NMAX],lg,maxim,sol,curr,st,solst,soldr;
struct Trie
{
Trie *fii[2];
int start;
Trie() {
memset(fii,0,sizeof(fii));
start=0;
}
};
Trie *root=new Trie();
void inserare(Trie *nod, int pos, int ind)
{
bool bit=(1<<(lg-pos-1))&s[ind];
if(pos!=lg)
{
if(!(nod->fii[bit]))
nod->fii[bit]=new Trie();
inserare(nod->fii[bit],pos+1,ind);
}
else nod->start=ind;
}
int compar(Trie *nod, int pos, int ind)
{
bool bit=(1<<(lg-pos-1))&s[ind];
if(pos!=lg)
{
if(nod->fii[1-bit])
{
curr+=(1<<(lg-pos-1));
compar(nod->fii[1-bit],pos+1,ind);
}
else compar(nod->fii[bit],pos+1,ind);
}
else return nod->start;
}
int main()
{
fi>>n;
for(int i=1;i<=n;i++)
{
fi>>s[i];
s[i]^=s[i-1];
maxim=max(s[i],maxim);
}
for(lg=0;(1<<lg)<=maxim;lg++);
inserare(root,0,1);
sol=s[1];
solst=1;
soldr=1;
for(int i=2;i<=n;i++)
{
if(s[i]>sol)
{
sol=s[i];
solst=1;
soldr=i;
}
curr=0;
st=compar(root,0,i);
if(curr>sol)
{
sol=curr;
solst=st+1;
soldr=i;
}
inserare(root,0,i);
}
fo<<sol<<" "<<solst<<" "<<soldr<<"\n";
fi.close();
fo.close();
return 0;
}