Pagini recente » Cod sursa (job #1150882) | Cod sursa (job #2438422) | Cod sursa (job #1191124) | Cod sursa (job #309147) | Cod sursa (job #350833)
Cod sursa(job #350833)
#include <stdio.h>
#include <string.h>
#define MAXN 100000
#define NBITS 21
#define MAXVAL ((1 << NBITS) - 1)
#define TRIESIZE (1 << NBITS)
int A[MAXN];
int values[MAXN + 1];
int childs[TRIESIZE][2];
int lastval, lastnode;
void trieadd(int key, int val)
{
int i, j, k;
for (i = 0, j = NBITS - 1; j >= 0; j--) {
k = (key >> j) & 1;
if (!childs[i][k])
childs[i][k] = j ? ++lastnode : ++lastval;
i = childs[i][k];
}
values[i] = val;
}
int triequery(int *key)
{
int i, j, k, key1, key2;
key1 = *key;
key2 = 0;
for (i = 0, j = NBITS - 1; j >= 0; j--) {
k = (key1 >> j) & 1;
if (childs[i][k]) {
i = childs[i][k];
if (k)
key2 |= 1 << j;
} else {
i = childs[i][1 - k];
if (!k)
key2 |= 1 << j;
}
}
*key = key2;
return values[i];
}
int main()
{
int N;
int bestxor, beststart, bestend;
int i, j, x, y;
freopen("xormax.in", "rt", stdin);
freopen("xormax.out", "wt", stdout);
scanf("%d", &N);
for (i = 0; i < N; i++)
scanf("%d", A + i);
bestxor = A[0];
beststart = bestend = 0;
trieadd(0, -1);
x = 0;
for (i = 0; i < N; i++) {
x ^= A[i];
y = x ^ MAXVAL;
j = triequery(&y);
y ^= x;
if (bestxor < y) {
bestxor = y;
beststart = j + 1;
bestend = i;
}
trieadd(x, i);
}
printf("%d %d %d\n", bestxor, beststart + 1, bestend + 1);
return 0;
}