Pagini recente » Cod sursa (job #1533664) | Cod sursa (job #532979) | Istoria paginii runda/winners8/clasament | Autentificare | Cod sursa (job #214741)
Cod sursa(job #214741)
#include <cstdio>
const int MAX_N = 100010;
int n, max, sol, s, nsol, s1, s2;
int b, p, x, z, nod;
int a[MAX_N], t[MAX_N][2], c[32], r[MAX_N];
void search(int i)
{
int nod = 1, put = 1 << b;
while (put > 1)
{
put >>= 1;
int q = a[i] & put;
if (q) q = 1;
if (t[nod][1-q])
{
nod = t[nod][1-q];
s += put;
}
else nod = t[nod][q];
}
nsol = r[nod];
}
void construct()
{
int i, j;
for (i = 1; i <= n; ++i)
{
x = a[i];
p = 0;
while (x)
{
c[++p] = x % 2;
x /= 2;
}
for (j = p + 1; j <= b; ++j) c[j] = 0;
nod = 1;
for (j = b; j > 0; --j)
{
if (t[nod][c[j]]) nod = t[nod][c[j]];
else
{
++z;
t[nod][c[j]] = z;
nod = z;
}
r[nod] = i;
}
}
}
int main()
{
int i, j;
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
max = a[1];
for (i = 2; i <= n; ++i)
{
a[i] ^= a[i-1];
if (max < a[i])
{
max = a[i];
s1 = 1;
s2 = i;
}
}
while (max)
{
++b;
max /= 2;
}
z = 1;
construct();
for (i = 0; i <= n; ++i)
{
s = 0;
search(i);
if (s > sol)
{
sol = s;
s1 = i + 1;
s2 = nsol;
}
}
printf("%d %d %d\n", sol, s1, s2);
return 0;
}