Pagini recente » Cod sursa (job #2866144) | Cod sursa (job #2972685) | Cod sursa (job #3288720) | Cod sursa (job #1909772) | Cod sursa (job #602736)
Cod sursa(job #602736)
#include <fstream.h>
#define MAXC 1024000
struct nod
{
int end;
long l0,r1;
};
nod Nodes[MAXC];
long root=0, K=0;
int n;
#define MAXP 22
long pow2[MAXP];
ifstream in("xormax.in");
ofstream out("xormax.out");
long newnode(int end)
{
K++;
Nodes[K].l0=Nodes[K].r1=-1;
Nodes[K].end = end;
};
void InsertX(unsigned long XoR, int end)
{
int i, is1;
long r = root;
for(i=20;i>0;i--)
{
is1 = ((XoR & pow2[i]) > 0);
if(is1)
{
if(Nodes[r].r1!=-1)
r=Nodes[r].r1;
else
r=Nodes[r].r1=newnode(-2);
}
else
{
if(Nodes[r].l0!=-1)
r=Nodes[r].l0;
else
r=Nodes[r].l0=newnode(-2);
}
}
is1 = ((XoR & pow2[0])>0);
if(is1)
r=Nodes[r].r1=newnode(end);
else
r=Nodes[r].l0=newnode(end);
};
struct Fres
{
int end;
unsigned long val;
};
Fres FindX(unsigned long best)
{
unsigned long vl = 0;
long r = root;
int i, is1;
for(i=20;i>0;i--)
{
is1 = ((best & pow2[i]) > 0);
is1 = 1 - is1;
if(is1)
{
if(Nodes[r].r1!=-1)
{r=Nodes[r].r1; vl += pow2[i];}
else
{r=Nodes[r].l0; vl += 0; }
}
else
{
if(Nodes[r].l0!=-1)
{ r=Nodes[r].l0; vl += pow2[i]; }
else
{ r=Nodes[r].r1; vl += 0; }
}
}
Fres res;
res.val = vl;
res.end = r.end;
}
int main()
{
in>>n;
int i;
pow2[0]=1;
for(i=1;i<MAXP;i++)
pow2[i]=pow2[i-1]*2;
InsertX(0,-1);
unsigned long XoRcur = 0;
unsigned long opt = -1;
int start = -1;
int end = -1;
for(i=0;i<n;i++)
{
unsigned long x;
in>>x;
XoRcur = XoRcur ^ x;
Fres R = FindX(~XoRcur);
if(R.val > opt)
{
opt = R.val;
start = R.end+1;
end = i;
}
InsertX(XoRcur, i);
}
out<<opt<<" "<<start+1<<" "<<end+1<<"\n";
return 0;
}