Pagini recente » Istoria paginii runda/oji_training0 | Cod sursa (job #463064) | Cod sursa (job #2481700) | Cod sursa (job #2810374) | Cod sursa (job #581275)
Cod sursa(job #581275)
#include <stdio.h>
int n,b,i,val,x[100001],poz,a,max;
bool s[27];
struct Trie{int poz; Trie *bit1; Trie *bit0;
Trie(){poz=-1; bit1=bit0=0;}};
Trie *t=new Trie;
int caut(Trie *nod,bool *s)
{
if (nod->poz>0 || (!nod->bit0 && !nod->bit1)) return nod->poz;
if (((*s) && nod->bit1) || (!*s) && !nod->bit0)
return caut(nod->bit1,s+1);
else
return caut(nod->bit0,s+1);
}
int ins(Trie *nod,bool *s)
{
if (poz>21)
{
nod->poz=i;
return 0;
}
if (*s)
{
if (!nod->bit0) nod->bit0=new Trie;
poz++;
ins(nod->bit0,s+1);
return 0;
}
if (!nod->bit1) nod->bit1=new Trie;
poz++;
ins(nod->bit1,s+1);
return 0;
}
int main(void)
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a);
x[i]=x[i-1]^a;
a=x[i];
for (poz=21;poz>=0;poz--)
{
s[poz]=(a%2);
a/=2;
}
if (i>1)
val=caut(t,s);
poz=0;
ins(t,s);
if (i>1 && x[i]^x[val]>max)
{
max=x[i]^x[val];
a=val+1;
b=i;
}
}
printf("%d %d %d\n",max,a,b);
return 0;
}