Pagini recente » Cod sursa (job #2072147) | Cod sursa (job #2637079) | Cod sursa (job #2372249) | Cod sursa (job #2835970) | Cod sursa (job #581266)
Cod sursa(job #581266)
#include <stdio.h>
int n,b,i,val,x[100001],poz,a,max;
char s[27];
struct Trie{int poz; Trie *bit1; Trie *bit0;
Trie(){poz=-1; bit1=bit0=0;}};
Trie *t=new Trie;
int caut(Trie *nod,char *s)
{
if (nod->poz>0 || (!nod->bit0 && !nod->bit1)) return nod->poz;
if ((*s-'0'==0 && nod->bit1) || (*s-'0'==1 && !nod->bit0))
return caut(nod->bit1,s+1);
else
return caut(nod->bit0,s+1);
}
int ins(Trie *nod,char *s)
{
if (*s=='\0')
{
nod->poz=i;
return 0;
}
if (*s=='0')
{
if (!nod->bit0) nod->bit0=new Trie;
ins(nod->bit0,s+1);
return 0;
}
if (!nod->bit1) nod->bit1=new Trie;
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]='0'+a%2;
a/=2;
}
s[22]='\0';
if (i>1)
val=caut(t,s);
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;
}