Pagini recente » Cod sursa (job #435302) | Cod sursa (job #267220) | Cod sursa (job #353578) | Cod sursa (job #2927566) | Cod sursa (job #218693)
Cod sursa(job #218693)
#include <stdio.h>
#include <math.h>
#define MAXN 100001
#define cnt 10
long n, m, nst, pos, xmax, imax, jmax, lmin, a[MAXN], t[MAXN * cnt], TRIE[MAXN * cnt][2], i, v, nb;
long Query(long v) {
long 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;
}
void BagaTrie(long v, long pos) {
long 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 Build() {
for (long i = 1; i <= n; ++i) {
BagaTrie(a[i], i);
}
BagaTrie(0, 0);
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
scanf("%ld", &n);
for (i = 1; i <= n; ++i) {
scanf("%ld", &v);
a[i] = a[i - 1] ^ v;
nb = 1;
while(v) {
++nb;
v >>= 1;
}
m = nb > m ? nb : m;
}
Build();
for (i = 0, xmax = -1; 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;
}
}
}
}
printf("%ld %ld %ld", xmax, imax, jmax);
return 0;
}