Pagini recente » Cod sursa (job #992086) | Cod sursa (job #2634112) | Cod sursa (job #2097133) | Cod sursa (job #2486780) | Cod sursa (job #462983)
Cod sursa(job #462983)
#include <stdio.h>
struct trie
{
trie *fiu[2];
trie ()
{
fiu[0] = fiu[1] = 0;
}
};
int n, sp[100002], last[1 << 21];
void add_trie (trie *t, int x, int p, int i)
{
if (p < 0)
return;
int bit = (x & (1 << p)) > 0;
if (!p)
last[x] = i;
if (!t -> fiu[bit])
t -> fiu[bit] = new trie;
add_trie (t -> fiu[bit], x, p - 1, i);
}
int find_trie (trie *t, int x, int p)
{
if (p < 0)
return 0;
int bit = (x & (1 << p)) > 0;
if (t -> fiu[bit ^ 1])
return find_trie (t -> fiu[bit ^ 1], x, p - 1) + ((bit ^ 1) << p);
if (t -> fiu[bit])
return find_trie (t -> fiu[bit], x, p - 1) + (bit << p);
return 0;
}
int main ()
{
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
scanf ("%d", &n);
trie *t = new trie;
int i, x, y, max = 0, st, dr;
for (i = 1; i <= n; i ++)
{
scanf ("%d", &x);
sp[i] = sp[i - 1] ^ x;
y = find_trie (t, sp[i], 20);
if (y ^ sp[i] > max)
{
max = y ^ sp[i];
st = last[y] + 1;
dr = i;
}
add_trie (t, sp[i], 20, i);
}
printf ("%d %d %d\n", max, st, dr);
return 0;
}