Cod sursa(job #2231094)

Utilizator DenisacheDenis Ehorovici Denisache Data 12 august 2018 22:28:41
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <set>

using namespace std;

struct BestXorInfo {
	uint32_t Value;
	uint32_t Position;
};

struct TrieNode {
	BestXorInfo xorInfo;
	vector< TrieNode* > children;

	TrieNode() {
		children.resize(2, nullptr);
	}
};

void Insert(TrieNode* node, const char* insertedString, const BestXorInfo& insertedInfo) {
	if (*insertedString == '\0') {
		node->xorInfo = move(insertedInfo);
		return;
	}

	if (node->children[*insertedString - '0'] == nullptr) {
		node->children[*insertedString - '0'] = new TrieNode();
	}

	Insert(node->children[*insertedString - '0'], insertedString + 1, insertedInfo);
}

BestXorInfo GetBestXor(TrieNode* node, const char* queriedString) {
	if (*queriedString == '\0') {
		return node->xorInfo;
	}

	if (node->children[1 - (*queriedString - '0')] != nullptr)
		return GetBestXor(node->children[1 - (*queriedString - '0')], queriedString + 1);
	else if (node->children[*queriedString - '0'] != nullptr)
		return GetBestXor(node->children[*queriedString - '0'], queriedString + 1);
}

int main() {
	ios::sync_with_stdio(false);

	ifstream cin("xormax.in");
	ofstream cout("xormax.out");

	uint32_t n;
	cin >> n;

	uint32_t currentXor = 0;

	uint32_t bestXor = 0;
	uint32_t bestLeft = 0;
	uint32_t bestRight = 0;

	TrieNode* root = new TrieNode();

	BestXorInfo currentInfo;
	currentInfo.Value = 0;
	currentInfo.Position = 0;

	Insert(root, bitset<22>(0).to_string().c_str(), currentInfo);

	for (uint32_t i = 1; i <= n; ++i) {
		uint32_t x;
		cin >> x;

		currentXor ^= x;
		bitset<22> bs(currentXor);

		currentInfo.Value = currentXor;
		currentInfo.Position = i;

		Insert(root, bs.to_string().c_str(), currentInfo);
		BestXorInfo bestXorInfo = GetBestXor(root, bs.to_string().c_str());

		if ((currentXor ^ bestXorInfo.Value) > bestXor) {
			bestXor = currentXor ^ bestXorInfo.Value;
			bestLeft = bestXorInfo.Position + 1;
			bestRight = i;
		}
	}

	if (bestLeft == 0) bestLeft = bestRight = 1;
	cout << bestXor << " " << bestLeft << " " << bestRight;

	//system("pause");
	return 0;
}