Cod sursa(job #2231105)

Utilizator DenisacheDenis Ehorovici Denisache Data 12 august 2018 23:20:10
Problema Xor Max Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 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;
};

BestXorInfo insertedInfo;
char trieString[22];
int idx = -1;

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

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

	void Insert() {
		if (++idx >= 22) {
			xorInfo = move(insertedInfo);
			return;
		}

		if (children[trieString[idx] - '0'] == nullptr) {
			children[trieString[idx] - '0'] = new TrieNode();
		}

		children[trieString[idx] - '0']->Insert();
	}

	BestXorInfo GetBestXor() {
		if (++idx >= 22) {
			return xorInfo;
		}

		if (children[1 - (trieString[idx] - '0')] != nullptr)
			return children[1 - (trieString[idx] - '0')]->GetBestXor();
		else if (children[trieString[idx] - '0'] != nullptr)
			return children[trieString[idx] - '0']->GetBestXor();
	}
};

void convertToBinaryString(uint32_t x) {
	int cnt = 21;

	while (x > 0) {
		trieString[cnt--] = '0' + (x & 1);
		x >>= 1;
	}

	while (cnt >= 0)
		trieString[cnt--] = '0';
}

int main() {
	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();

	insertedInfo.Value = 0;
	insertedInfo.Position = 0;

	convertToBinaryString(0);
	root->Insert();
	idx = -1;

	uint32_t x; 
	BestXorInfo bestXorInfo;

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

		currentXor ^= x;

		insertedInfo.Value = currentXor;
		insertedInfo.Position = i;

		convertToBinaryString(currentXor);
		root->Insert();
		idx = -1;
		bestXorInfo = root->GetBestXor();
		idx = -1;

		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;
}