Cod sursa(job #633603)

Utilizator calinuxIorgulescu Calin calinux Data 14 noiembrie 2011 05:16:44
Problema Xor Max Scor 35
Compilator c Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <string.h>

#define MaxN 100000

struct trie_node {
	struct trie_node *child[2];
	int idx;
} *trie_root;

int n;
int x[MaxN + 1];
int soli, solj, solmax;

void trie_insert(struct trie_node **root, int value, int idx) {

	int bit;
	struct trie_node *tmp;

	if (*root == NULL)
		*root = (struct trie_node *)calloc(1, sizeof(struct trie_node));

	tmp = *root;

	for (bit = 21 ; bit >= 0 ; bit--) {

		int cur_bit = value & (1 << bit) ? 1 : 0;

		if (tmp -> child[cur_bit] == NULL)
			tmp -> child[cur_bit] = (struct trie_node *)calloc(1, sizeof(struct trie_node));

		tmp = tmp -> child[cur_bit];

	}

	tmp -> idx = idx;

}

void read(void) {

	int i;
	freopen("xormax.in", "r", stdin);

	scanf("%d\n", &n);

	for (i = 0 ; i < n ; i++) {
		scanf("%d ", x + i);
		if (i)
			x[i] ^= x[i - 1];
		trie_insert(&trie_root, x[i], i);

		if (x[i] > solmax) {
			solmax = x[i];
			solj = i;
		}
	}

}

void solve(void) {

	int i, bit, val;
	struct trie_node* tmp;

	for (i = 1 ; i < n ; i++) {

		tmp = trie_root;

		val = 0;

		for (bit = 21 ; bit >= 0 ; bit --) {

			int rev_cur_bit = x[i] & (1 << bit) ? 0 : 1;

			if (tmp -> child[rev_cur_bit] == NULL)
				tmp = tmp -> child[1 - rev_cur_bit];
			else {
				tmp = tmp -> child[rev_cur_bit];
				val ^= (1 << bit);
			}

		}

		if (val > solmax && tmp -> idx < i) {
			solmax = val;
			solj = i;
			soli = tmp -> idx + 1;
		}
	}

}


void write(void) {

	freopen("xormax.out", "w", stdout);
	printf("%d %d %d\n", solmax, soli + 1, solj + 1);

}

int main(void) {


	read();
	solve();
	write();
	return 0;

}