Cod sursa(job #2231054)

Utilizator DenisacheDenis Ehorovici Denisache Data 12 august 2018 20:00:14
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <set>

using namespace std;

string toBinaryString(int x) {
	string binaryRepr = ""s;

	while (x > 0) {
		binaryRepr += char('0' + (x & 1));
		x >>= 1;
	}

	if (binaryRepr.empty()) binaryRepr = "0"s;

	return binaryRepr + string(22 - binaryRepr.size(), '0');
}

struct BestXorInfo {
	int Value;
	int Position;
};

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

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

	void Insert(const char* insertedString, const BestXorInfo& insertedInfo, int idx) {
		if (idx == -1) {
			this->xorInfo.Value = insertedInfo.Value;
			this->xorInfo.Position = max(this->xorInfo.Position, insertedInfo.Position);
			
			return;
		}

		char lastChar = insertedString[idx];

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

		children[lastChar - '0']->Insert(insertedString, insertedInfo, idx - 1);
	}

	BestXorInfo GetBestXor(const char* queriedString, int idx) {
		if (idx == -1) {
			return xorInfo;
		}

		char lastChar = queriedString[idx];

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

class Trie {
	TrieNode root;

public:
	void Insert(string& insertedString, const BestXorInfo& insertedInfo) {
		root.Insert(insertedString.c_str(), insertedInfo, insertedString.size() - 1);
	}

	BestXorInfo GetBestXor(string& queriedString) {
		return root.GetBestXor(queriedString.c_str(), queriedString.size() - 1);
	}
};

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

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

	int n;
	cin >> n;

	int currentXor = 0;

	int bestXor = 0;
	int bestLeft = -1;
	int bestRight = -1;

	Trie trie;
	string zeroRepr = toBinaryString(0);
	trie.Insert(zeroRepr, { 0, 0 });

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

		currentXor ^= x;
		
		string binaryRepr = toBinaryString(currentXor);
		string auxRepr = binaryRepr;

		BestXorInfo bestXorInfo = trie.GetBestXor(auxRepr);
		trie.Insert(binaryRepr, { currentXor, i });

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

	cout << bestXor << " " << bestLeft << " " << bestRight;

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