Pagini recente » Cod sursa (job #773072) | Cod sursa (job #971844) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #365556)
Cod sursa(job #365556)
#include <stdio.h>
#define nmax 100005
#define B 21
struct Trie
{
int k;
Trie *fiu [2];
Trie ()
{
k=0;
fiu [0]=fiu [1]=0;
}
};
int r=-1, w, n, p, first, last, v [nmax], xp [nmax];
Trie *t=new Trie;
void scan ()
{
int i;
scanf ("%d", &n);
for (i=1; i <= n; ++i)
{
scanf ("%d", &v [i]);
xp [i]=xp [i-1]^v [i];
}
}
void add (Trie *k, int b)
{
if (b == -1)
{
k->k=p;
return;
}
int cv=w & (1 << b);
if (cv)
cv=1;
if (k->fiu [cv] == 0)
k->fiu [cv]=new Trie;
add (k->fiu [cv], b-1);
}
int cauta (Trie *k, int b)
{
if (b == -1)
return k->k;
int cv=w & (1 << b);
if (cv)
cv=1;
if ((k->fiu [cv]) == 0)
{
if (cv == 0)
cv=1;
else
cv=0;
}
if (k->fiu [cv] == 0)
return 0;
return cauta (k->fiu [cv], b-1);
}
void rez ()
{
int i, k;
w=0;
p=0;
add (t, 21);
for (i=1; i <= n; ++i)
{
w= ~xp [i];
k=cauta (t, 21);
fprintf(stderr, "%d %d %d %d\n", i, xp [i], w, k);
if (r < (xp [i]^xp [k]))
{
r=xp [i]^xp [k];
first=k+1;
last=i;
}
w=xp [i];
p=i;
add (t, 21);
}
}
int main ()
{
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
scan ();
rez ();
printf ("%d %d %d\n", r, first, last);
return 0;
}