Pagini recente » Cod sursa (job #2569286) | Cod sursa (job #1738638) | Cod sursa (job #2863923) | Cod sursa (job #572106) | Cod sursa (job #142672)
Cod sursa(job #142672)
#include <cstdio>
#define dim 100001
#define cnst 10
int A[dim], Trie[cnst*dim][2], T[cnst*dim];
int N;
int M;
int X;
int Nst;
void BagaTrie(int v, int i)
{
int b, nb, st = 0;
nb = M - 1;
while(nb >= 0)
{
b = (v >> nb) & 1;
if(!Trie[st][b])
{
Trie[st][b] = ++ Nst;
st = Nst;
}
else
st = Trie[st][b];
-- nb;
}
if(!T[st]) T[st] = i;
}
int Query(int v)
{
int st, nb, ret = 0;
nb = M - 1;
st = 0;
while(nb >= 0)
{
int b = (v >> nb) & 1;
if(Trie[st][!b])
{
ret |= (1 << nb);
st = Trie[st][!b];
}
else
st = Trie[st][b];
-- nb;
}
X = st;
return ret;
}
int main()
{
freopen("xormax.in", "rt", stdin);
freopen("xormax.out", "wt", stdout);
int i;
int v;
int nb;
int max;
for(scanf("%d", &N), i=1; i<=N; ++i)
{
scanf("%d", &v);
A[i] = A[i-1] ^ v;
v = A[i];
nb = 0;
while(v) ++ nb, v >>= 1;
M = nb > M ? nb : M;
}
int imax = 0;
int jmax = 0;
int lmin = N + 1;
max = 0;
for(i=1; i<=N; ++i)
{
BagaTrie(A[i], i);
if(A[i] > max) max = A[i], imax = 1, jmax = i, lmin = i;
}
for(i=1; i<N; ++i)
{
v = Query(A[i]);
if(T[X] > i)
{
if(v > max) max = v, imax = i + 1, jmax = T[X], lmin = T[X] - i;
else if(v == max && T[X] < jmax) imax = i + 1, jmax = T[X], lmin = T[X] - i;
else if(v == max && T[X] == jmax && T[X]-i < lmin) imax = i + 1, jmax = T[X], lmin = T[X] - i;
}
}
if(jmax < imax) for(;;);
printf("%d %d %d", max, imax, jmax);
fclose(stdin);
fclose(stdout);
return 0;
}