Cod sursa(job #2003497)

Utilizator mircea_marian.popaPopa Mircea-Marian mircea_marian.popa Data 22 iulie 2017 23:46:45
Problema Xor Max Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 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]];
	}
	if(!node->index)
		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{
			node = node->children[bits[bitIndex]];
			mask += bits[bitIndex] << bitIndex;
		}

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

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

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 = 1;
	addToTrie(root, g_max, 0);

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

		if(
			index != BAD_VALUE
			&& (bestSum ^ l_sum) > g_max
		){
			g_st = index + 1;
			g_fi = i;
			g_max = bestSum ^ l_sum;
		}

		addToTrie(root, l_sum, i);
	}
	
	file.close();
	freeTrie(root);
	
	file.open("xormax.out", ios::out);
	file << g_max << " " << g_st + 1 << " " << g_fi + 1;
	file.close();
	
	return 0;
}