Pagini recente » Cod sursa (job #1298705) | Cod sursa (job #406731) | Cod sursa (job #79898) | Cod sursa (job #359386) | Cod sursa (job #142679)
Cod sursa(job #142679)
#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 = 0;
int imax = 0;
int jmax = 0;
int lmin = N + 1;
for(scanf("%d", &N), i=1; i<=N; ++i)
{
scanf("%d", &v);
A[i] = A[i-1] ^ v;
if(v > max) max = v, imax = i, jmax = i, lmin = 1;
v = A[i];
nb = 0;
while(v) ++ nb, v >>= 1;
M = nb > M ? nb : M;
}
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;
}
}
int smax = 0;
for(i=0; i<N; ++i)
for(int j=i+1; j<=N; ++j)
{
int s = A[j] ^ A[i];
if(smax < s) smax = s;
}
if(max != smax) for(;;);
printf("%d %d %d", max, imax, jmax);
fclose(stdin);
fclose(stdout);
return 0;
}