Pagini recente » Cod sursa (job #3282335) | Cod sursa (job #132020) | Cod sursa (job #2880819) | Cod sursa (job #3120600) | Cod sursa (job #2470010)
#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,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])
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;
}
st=compar(root,0,i);
if(s[i]^s[st]>sol)
{
sol=s[i]^s[st];
solst=st+1;
soldr=i;
}
inserare(root,0,i);
}
fo<<sol<<" "<<solst<<" "<<soldr<<"\n";
fi.close();
fo.close();
return 0;
}