Pagini recente » Cod sursa (job #1836217) | Cod sursa (job #2308973) | Cod sursa (job #1370456) | Cod sursa (job #290638) | Cod sursa (job #142827)
Cod sursa(job #142827)
#include <cstdio>
#define dim 100001
#define cnt 10
int N;
int M;
int Nst;
int Pos;
int Xmax;
int Imax;
int Jmax;
int Lmin;
int A[dim];
int T[dim*cnt];
int Trie[dim*cnt][2];
void ReadData();
void Build();
void BagaTrie(int, int);
void Solve();
void Write();
int Query(int v)
{
int b, nb, ret, st;
for(ret=st=0, nb=M-1; nb>=0; --nb)
{
b = (v >> nb) & 1;
if(Trie[st][!b])
{
ret |= (1 << nb);
st = Trie[st][!b];
}
else
st = Trie[st][b];
}
Pos = st;
return ret;
}
int main()
{
ReadData();
Build();
Solve();
Write();
return 0;
}
void ReadData()
{
freopen("xormax.in", "rt", stdin);
int i, v, nb;
for(scanf("%d", &N), i=1; i<=N; ++i)
{
scanf("%d", &v);
A[i] = A[i-1] ^ v;
nb = 0;
while(v) ++ nb, v >>= 1;
M = nb > M ? nb : M;
}
fclose(stdin);
}
void Build()
{
int i;
for(i=1; i<=N; ++i)
BagaTrie(A[i], i);
BagaTrie(0, 0);
}
void BagaTrie(int v, int pos)
{
int st = 0, nb, b;
for(nb=M-1; nb>=0; --nb)
{
b = (v >> nb) & 1;
if(!Trie[st][b])
{
Trie[st][b] = ++ Nst;
st = Nst;
}
else
st = Trie[st][b];
}
if(!T[st]) T[st] = pos;
}
void Solve()
{
int i, v;
for(i=0; i<N; ++i)
{
v = Query(A[i]);
if(T[Pos] <= i) continue;
if(v > Xmax)
{
Xmax = v;
Imax = i + 1;
Jmax = T[Pos];
Lmin = Jmax - i;
}
else if(v == Xmax && T[Pos] < Jmax)
{
Imax = i + 1;
Jmax = T[Pos];
Lmin = Jmax - i;
}
else if(v == Xmax && T[Pos] == Jmax && T[Pos] - i < Lmin)
{
Imax = i + 1;
Lmin = T[Pos] - i;
}
}
}
void Write()
{
freopen("xormax.out", "wt", stdout);
printf("%d %d %d", Xmax, Imax, Jmax);
int i, ok;
if(Imax == Jmax)
for(i=1, ok=0; i<=N; ++i)
if(A[i] ^ A[i-1] == Xmax) ok = 1;
if(!ok) for(;;);
fclose(stdout);
}