Pagini recente » Cod sursa (job #191728) | Cod sursa (job #31214) | Cod sursa (job #2079071) | Cod sursa (job #1229366) | Cod sursa (job #161798)
Cod sursa(job #161798)
/*
PROB: cowxor
LANG: C
ID: marius.2
*/
#include <stdio.h>
#include <assert.h>
#define M 21
#define MAXN 100000
static short int c [(1 << M) + 1];
static int e [(1 << M) + 1];
static int a[MAXN + 2], b[MAXN + 2], d[MAXN + 2], n;
static int bestx, bestj;
static void heap_shift (int * a, int start, int count) {
int root, child, aux;
root = start;
while ((child = 2 * root + 1) < count) {
if (child < count - 1 && a [child] < a [child + 1]) ++ child;
if (a [root] < a [child]) {
aux = a [root]; a [root] = a [child]; a [child] = aux;
root = child;
} else return;
}
}
static void heap_sort (int * a, int count) {
int start, end, aux;
start = count / 2 - 1; end = count - 1;
while (start >= 0) {
heap_shift (a, start, count);
-- start;
}
while (end > 0) {
aux = a [0]; a [0] = a [end]; a [end] = aux;
heap_shift (a, 0, end);
-- end;
}
}
int main() {
FILE * fin, * fout;
int i, j, k;
fin = fopen("xormax.in", "r");
fout = fopen("xormax.out", "w");
fscanf(fin, "%d", &n);
for (i = 0, b[0] = 0; i < n; i++) {
fscanf(fin, "%d", & a[i]);
b [i + 1] = b [i] ^ a[i];
}
fclose (fin);
for (i = 0; i <= n; i ++) d [i] = b [i];
heap_sort (d, n + 1);
i = j = 0;
while (i <= n) {
while (d[i] >= j) c[j++] = i;
while (i <= n && d[i] < j) i++;
}
while (j <= (1 << M)) c[j++] = i;
for (i = 0; i <= (1 << M); i++) e[i] = -1;
for (i = 0; i <= n; i++) if (e [b [i]] == -1) e [b [i]] = i;
bestx = -1;
for (j = 1; j <= n; j++) {
for (k = 0, i = M-1; i >= 0; i--) {
if ((c [k + (1 << (i + 1))] - c[k + (1 << i)]) == 0) continue;
if ((c[k+(1<<i)] - c[k]) == 0 || ((b[j] >> i) & 1) == 0) k |= (1 << i);
}
assert (0 <= k);
assert (k <= (1<<M));
assert (e [k] != -1);
if (e [k] > j) continue;
if ((k ^ b[j]) <= bestx) continue;
bestj = j;
bestx = k ^ b[j];
if (bestx == ((1 << M) - 1)) break;
}
j = bestj;
i = j;
while ((b [i] ^ b [j]) != bestx) i --;
if (i + 1 > j) i = j; else i = i + 1;
fprintf(fout, "%d %d %d\n", bestx, i, j);
fclose (fout);
return 0;
}