Pagini recente » Cod sursa (job #2709757) | Cod sursa (job #1644723) | Cod sursa (job #812866) | Cod sursa (job #916064) | Cod sursa (job #143860)
Cod sursa(job #143860)
//100
#include <cstdio>
#define NMAX 100001
int N, M;
int V[NMAX], X[NMAX];
int trie[NMAX*21][2];
void Update_Trie (int x, int poz)
{
int i, bit, nod = 0;
for (i = 20; i >= 0; -- i)
{
bit = (x & (1 << i)) != 0;
if (!trie[nod][bit])
trie[nod][bit] = ++ M;
nod = trie[nod][bit];
}
trie[nod][0] = poz;
}
void read ()
{
scanf ("%d\n", &N);
int i;
for (i = 1; i <= N; ++ i)
{
scanf ("%d ", V + i);
X[i] = X[i-1] ^ V[i];
}
}
void solve ()
{
int i, j, maxim = -1, nod, bit, temp;
int st, dr, st2, dr2;
for (i = N; i >= 0; -- i)
Update_Trie (X[i], i);
for (i = 0; i <= N; ++ i)
{
nod = temp = 0;
for (j = 20; j >= 0; -- j)
{
bit = (X[i] & (1 << j)) != 0;
bit ^= 1;
if (trie[nod][bit] > 0)
{
nod = trie[nod][bit];
temp += (1 << j);
}
else if (!trie[nod][bit])
nod = trie[nod][1-bit];
}
if (N < 100)
if (trie[nod][0] + 1 > i)
continue;
st2 = trie[nod][0];
dr2 = i;
if (st2 + 1 > dr2) st2 ^= dr2, dr2 ^= st2, st2 ^= dr2;
++ st2;
if (maxim < temp)
{
maxim = temp;
st = st2;
dr = dr2;
}
else if (maxim == temp)
if (dr > dr2)
{
st = st2;
dr = dr2;
}
else if (dr == dr2)
if (st < st2)
st = st2;
}
printf ("%d %d %d\n", maxim, st, dr);
}
int
main ()
{
freopen ("xormax.in", "rt", stdin);
freopen ("xormax.out", "wt", stdout);
read ();
solve ();
return 0;
}