Pagini recente » Cod sursa (job #2534963) | Cod sursa (job #2860853) | Cod sursa (job #1962400) | Statistici Biraianu Alex Valentin (Alexbiraianu) | Cod sursa (job #591044)
Cod sursa(job #591044)
#include <cstdio>
#define l 20
#define lmax (1<<21)+3
int n, sol, r1, r2, v[lmax][2], vn[lmax][2], trie[lmax], h;
int getNext(int root, int c)
{
if (v[root][c]) return vn[root][c];
return -1;
}
void addTrie(int x, int p)
{
int i, c, root=0, next;
for (i=l; i>=0; i--)
{
c=x&(1<<i);
if (c>0) c=1;
next=getNext(root, c);
if (next==-1)
{
next=h;
h++;
trie[h]=p;
v[root][c]=1;
vn[root][c]=next;
} else trie[next]=p;
root=next;
}
}
void search(int x, int p)
{
int i, c, root=0, next, sum=0;
for (i=l; i>=0; i--)
{
c=x&(1<<i);
if (c>0) c=1;
c=!c;
next=getNext(root, c);
if (next==-1)
{
c=!c;
next=getNext(root, c);
} else sum+=(1<<i);
root=next;
}
if (sum>sol)
{
sol=sum;
r1=trie[root]+1;
r2=p;
}
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d", &n);
int i, x, s=0;
h=1;
for (i=1; i<=n; i++)
{
scanf("%d", &x);
s^=x;
if (i>1) search(s, i); else
{
sol=x;
r1=r2=i;
}
addTrie(s, i);
}
printf("%d %d %d\n",sol, r1, r2);
}