Pagini recente » Cod sursa (job #1645669) | Cod sursa (job #1776131) | Cod sursa (job #1689075) | Cod sursa (job #1690419) | Cod sursa (job #463005)
Cod sursa(job #463005)
#include <stdio.h>
struct trie
{
trie *fiu[2];
trie ()
{
fiu[0] = fiu[1] = 0;
}
};
int n, sp[100002], last[2100000];
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 (!bit)
{
if (t -> fiu[1])
return find_trie (t -> fiu[1], x, p - 1) + (1 << p);
else
return find_trie (t -> fiu[0], x, p - 1);
}
else
{
if (t -> fiu[0])
return find_trie (t -> fiu[0], x, p - 1);
else
return find_trie (t -> fiu[1], x, p - 1) + (1 << p);
}
}
int main ()
{
freopen ("xormax.in", "r", stdin);
freopen ("xormax.out", "w", stdout);
scanf ("%d", &n);
trie *t = new trie;
int i, x, y = 0, max = 0, st, dr;
for (i = 1; i <= n; i ++)
{
scanf ("%d", &x);
sp[i] = sp[i - 1] ^ x;
if (sp[i] > max)
{
max = sp[i];
st = dr = i;
}
if (i > 1)
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;
}