Cod sursa(job #978752)
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int A,x,st,dr,poz,pot,cur,j,S,a,t,n,best,i;
char s[30];
struct Trie
{
int po;
Trie *fiu[2];
Trie()
{
po=0;
memset(fiu,0,sizeof(fiu));
}
};
Trie *r=new Trie;
int find(Trie *nod,char *p)
{
if(*p=='a')
return 1;
if(nod->fiu[*p]!=NULL)
return find(nod->fiu[*p],p+1);
return 0;
}
void insert(Trie *nod,char *p)
{
if(*p=='a')
{
nod->po=i;
return ;
}
if(nod->fiu[*p]==NULL)
{
nod->fiu[*p]=new Trie;
}
insert(nod->fiu[*p],p+1);
}
void solut(Trie *nod,char *p)
{
pot>>=1;
if(*p=='a')
{
poz=nod->po;
return ;
}
if(nod->fiu[!(*p)]!=NULL)
{
A+=pot*(!(*p));
solut(nod->fiu[!(*p)],p+1);
}
else
{
A+=pot*(*p);
solut(nod->fiu[*p],p+1);
}
}
int main ()
{
f>>n;
best=0;
for(i=0;i<23;++i)
s[i]=0;
s[23]='a';
i=0;
insert(r,s);
best=-1;
for(i=1;i<=n;++i)
{
f>>x;
S^=x;
a=S;
t=-1;
while(a)
{
t++;
if(a&1)
s[t]=1;
else
s[t]=0;
a>>=1;
}
for(j=0;j<=11;++j)
swap(s[j],s[22-j]);
A=0;
pot=(1<<23);
solut(r,s);
cur=A^S;
if(cur>best)
{ best=cur,st=poz,dr=i; }
if(!find(r,s))
insert(r,s);
memset(s,0,23);
}
g<<best<<" "<<st+1<<" "<<dr;
return 0;
}