Cod sursa(job #1995637)

Utilizator mircea_marian.popaPopa Mircea-Marian mircea_marian.popa Data 28 iunie 2017 18:02:13
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <iostream>
#include <fstream>

#define BAD_VALUE 100000

using namespace std;

typedef struct Trie {
	unsigned int *index;
	struct Trie *children[2];
} TrieT, *TrieP;

void addToTrie(TrieP node, const unsigned int value, const unsigned int arrayIndex){
	unsigned char bitIndex = 21;
	bool bits[21];
	unsigned int mask = 1 << 20;
	while(bitIndex--){
		bits[bitIndex] = (bool)(value & mask);
		mask >>= 1;
	}

	bitIndex = 21;
	TrieP newCell;
	while(bitIndex--){
		if(node->children[bits[bitIndex]] == NULL){
			newCell = new TrieT;
			newCell->index = NULL;
			newCell->children[0] = newCell->children[1] =
				NULL;
			node->children[bits[bitIndex]] = newCell;
			node = newCell;
		} else
			node = node->children[bits[bitIndex]];
	}
	node->index = new unsigned int;
	*(node->index) = arrayIndex;
}

unsigned int getBestValue(TrieP node, unsigned int value, unsigned int &index){
	if(!node->children[0] && !node->children[1]){
		index = BAD_VALUE;
		return 0;
	}

	unsigned char bitIndex = 21;
	bool bits[21];
	unsigned int mask = 1 << 20;
	while(bitIndex--){
		bits[bitIndex] = (bool)(value & mask);
		mask >>= 1;
	}


	bitIndex = 21;
	mask = 0;
	while(bitIndex--)
		if(node->children[!bits[bitIndex]]){
			node = node->children[!bits[bitIndex]];
			mask += !bits[bitIndex] << bitIndex;
		}
		else{
			if(bits[bitIndex]){
				index = BAD_VALUE;
				return 0;
			}
			node = node->children[bits[bitIndex]];
			mask += bits[bitIndex] << bitIndex;
		}

	index = mask ? *(node->index) : BAD_VALUE;
	return mask;
}

void freeTrie(TrieP node){
	if(!node->children[0] && !node->children[1])
		delete node->index;
	else{
		if(node->children[0]){
			freeTrie(node->children[0]);
			delete node->children[0];
		}
		if(node->children[1]){
			freeTrie(node->children[1]);
			delete node->children[1];
		}
	}
}

int main() {
	fstream file ("xormax.in", ios::in);

	unsigned int N, l_sum, g_max, g_st, g_fi, value, index, bestSum;
	TrieP root = new TrieT;
	root->index = NULL;
	root->children[0] = root->children[1] = NULL;
	file >> N;
	file >> l_sum;
	g_max = l_sum;
	g_fi = g_st = 0;
	addToTrie(root, g_max, 0);

	for(unsigned i = 1; i < N; i++){
		file >> value;
		l_sum ^= value;
		addToTrie(root, l_sum, i);

		bestSum = getBestValue(root, l_sum, index);

		if(index != BAD_VALUE){
			g_st = index + 1;
			g_fi = i;
			g_max = bestSum ^ l_sum;
		}
	}
	file.close();
	freeTrie(root);
	file.open("xormax.out", ios::out);
	file << g_max << " " << g_st + 1 << " " << g_fi + 1;
	file.close();
	return 0;
}