Cod sursa(job #633864)

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

#define MaxN 100000

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

int n;
int soli, solj, solmax;

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

	int bit;
	struct trie_node *tmp = root;

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

		int cur_bit = !(value & bit);

		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, *trie_root;

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

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

	scanf("%d ", &sum);
	trie_root = (struct trie_node *)calloc(1, sizeof(struct trie_node));
	trie_insert(trie_root, sum, 0);
	solmax = sum;

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

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

		tmp = trie_root;
		val = 0;

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

			int rev_cur_bit = !!(sum & bit);

			if (tmp -> child[rev_cur_bit] == NULL)
				tmp = tmp -> child[!rev_cur_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;

}