Pagini recente » Cod sursa (job #2143621) | Cod sursa (job #3180796) | Cod sursa (job #2743851) | Cod sursa (job #3220267) | Cod sursa (job #1626066)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie
{
int xo,val;
trie *st,*dr;
trie()
{
xo=val=0;
st=dr=0;
}
};
trie *root=new trie;
void update(int pxor,int nr)
{
trie *nod=root;
for(int i=23;i>=0;i--)
{
bool ok=pxor &(1<<i);
if(ok==0)
{
if(nod->st==0) nod->st=new trie;
nod=nod->st;
}
else
{
if(nod->dr==0) nod->dr=new trie;
nod=nod->dr;
}
}
nod->xo=pxor;
nod->val=nr;
}
int cauta(int pxor,int &pos)
{
trie *nod=root;
for(int i=23;i>=0;i--)
{
bool ok=pxor&(1<<i);
if(ok==1&&nod->st!=0) nod=nod->st;
else if(ok==1) nod=nod->dr;
else if(ok==0&&nod->dr!=0) nod=nod->dr;
else nod=nod->st;
}
pos=nod->val;
return pxor^nod->xo;
}
int main()
{
int result=-1,pxor=0,n,i,j,step,pos1=0,pos2=0,pos;
update(pxor,1);
fin>>n;
for(i=1;i<=n;i++)
{
fin>>j;
pxor^=j;
update(pxor,i);
step=cauta(pxor,pos);
if(step>result)
{
result=step;
pos1=pos;pos2=i;
}
}
if(pos1==pos2) pos1--;
fout<<result<<" "<<pos1+1<<" "<<pos2;
}