Cod sursa(job #1455371)

Utilizator GilgodRobert B Gilgod Data 27 iunie 2015 20:08:53
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <assert.h>

const char IN[] = "xormax.in", OUT[] = "xormax.out";
const int NMAX = 100001;
const int ALPHABET = 2;
const int INF = 0x3f3f3f3f;
const int MAXBITRANK = 21;

struct node {
	int index, succs_count;
	node* succs[ALPHABET];
};

using namespace std;

int N;
node* trie;
int S[NMAX];

inline char get_bit(int const x, int rank) {
	return ((0x1 << rank) & x) ? 1 : 0;
}

void add_word(node* crt, int x, int rank, int pos) {
	if (rank == -1) {
		++crt->index = pos;
		return;
	}
	int key = get_bit(x, rank);
	if (crt->succs[key] == NULL) {
		++crt->succs_count;
		crt->succs[key] = new node();
	}
	add_word(crt->succs[key], x, rank - 1, pos);
}

void set(int &x, int rank) {
	x |= (0x1 << rank);
}

int find_flipped(node *crt, int x, int rank, int &s) {
	if (rank == -1 || crt->succs_count == 0) return crt->index;
	int key = 1 - (get_bit(x, rank));
	if (crt->succs[key] == NULL) return find_flipped(crt->succs[1-key], x, rank-1, s);
	set(s, rank);
	return find_flipped(crt->succs[key], x, rank - 1, s);
}

inline void read_data() {
	assert(freopen(IN, "r", stdin));
	assert(scanf("%d", &N));
	S[0] = 0;
	int best = 0, index1 = 0, index2 = 0;
	for (int i = 0, s = 0; i < N; ++i) {
		int x;
		assert(scanf("%d", &x));
		S[i + 1] = S[i] ^ x;
		s = 0;
		int ind = find_flipped(trie, S[i+1], MAXBITRANK, s);
		if (s > best) best = s, index1 = ind, index2 = i;
		add_word(trie, S[i+1], MAXBITRANK, i);
	} 
	fprintf(fopen(OUT, "w"), "%d %d %d\n", best, index1+2, index2+1);
	fclose(stdin);
}

int main() {
	trie = new node();
	trie->index = -1;
	trie->succs_count = 0;
	read_data();
	delete trie;
}