Pagini recente » Cod sursa (job #2002963) | Cod sursa (job #295430) | Cod sursa (job #2078031) | Cod sursa (job #2080619) | Cod sursa (job #132097)
Cod sursa(job #132097)
#include <cstdio>
#include <cassert>
#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, a, b, maxim = 0, nod, bit, temp;
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 (trie[nod][0] + 1 > i)
continue;
if (maxim < temp)
{
maxim = temp;
a = trie[nod][0] + 1;
b = i;
}
else if (maxim == temp)
if (a > trie[nod][0] + 1)
{
a = trie[nod][0] + 1;
b = i;
}
else if (a == trie[nod][0] + 1)
if (b > i)
b = i;
}
printf ("%d %d %d\n", maxim, a, b);
}
int
main ()
{
freopen ("xormax.in", "rt", stdin);
freopen ("xormax.out", "wt", stdout);
read ();
solve ();
return 0;
}