Pagini recente » Cod sursa (job #1178373) | Cod sursa (job #788980)
Cod sursa(job #788980)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Max 100001
struct trie{
struct trie*f[2];
int p;
trie(){ memset(f,0,sizeof(f)); p=0; } }*t;
int n,x[Max],xmax,p,p1,u;
void add(int x,int p)
{
trie *g=t;
int urm;
for(int i=20;i>=0;i--)
{
if(x&(1<<i))urm=1; else urm=0;
if(g->f[urm]==0)g->f[urm]=new trie;
g=g->f[urm];
}
g->p=p;
}
int find(int x)
{
trie *g=t;
int urm;
for(int i=20;i>=0;i--)
{
if(x&(1<<i))urm=0; else urm=1;
if(g->f[urm]==0)urm=!urm;
g=g->f[urm];
}
return g->p;
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x[i]);
x[i]^=x[i-1];
}
t=new trie;
add(x[1],1);
xmax=x[1]; p=u=1;
for(int i=2;i<=n;i++)
{
p1=find(x[i]);
if((x[p1]^x[i])>xmax){p=p1+1;u=i;xmax=x[p1]^x[i];}
add(x[i],i);
}
printf("%d %d %d\n",xmax,p,u);
return 0;
}