Cod sursa(job #161798)

Utilizator mgntMarius B mgnt Data 18 martie 2008 20:18:47
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
/*
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;
}