Cod sursa(job #633853)

Utilizator calinuxIorgulescu Calin calinux Data 14 noiembrie 2011 22:39:29
Problema Xor Max Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.45 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 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 = 1 << 21 ; bit > 0 ; bit >>= 1) {

		int cur_bit = value & 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 solve(void) {

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

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

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

	scanf("%d ", &sum);
	trie_insert(&trie_root, sum, 0);
	solmax = sum;

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

		scanf("%d ", &t);
		sum ^= t;

		tmp = trie_root;
		val = sum;

		for (bit = 1 << 21 ; bit > 0 ; bit >>= 1) {

			int rev_cur_bit = sum & bit == 0;

			if (tmp -> child[rev_cur_bit] == NULL) {
				tmp = tmp -> child[!rev_cur_bit];
				val &= ~bit;
			} else {
				tmp = tmp -> child[rev_cur_bit];
				val |= bit;
			}

		}

		trie_insert(&trie_root, sum, i);

		if (val > solmax) {
			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) {


	solve();
	write();
	return 0;

}