Cod sursa(job #2660744)

Utilizator mircearoataMircea Roata Palade mircearoata Data 20 octombrie 2020 13:27:09
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>

using namespace std;

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

class Trie {
public:
	Trie(int _val) : val(_val) {
		children[0] = children[1] = nullptr;
	}

	void add(const char* pos, const int& val) {
		if (*pos == '\0') {
			this->val = val;
			return;
		}
		if (!children[*pos - '0']) {
			children[*pos - '0'] = new Trie(0);
		}
		children[*pos - '0']->add(pos + 1, val);
	}

	Trie* findClose(const char* pos) {
		if (*pos == '\0') {
			return this;
		}
		if (children[*pos - '0']) {
			return children[*pos - '0']->findClose(pos + 1);
		}
		if (children[1 - (*pos - '0')]) {
			return children[1 - (*pos - '0')]->findClose(pos + 1);
		}
		return nullptr;
	}

	inline int getVal() { return val; }

private:
	int val;
	Trie* children[2];
};

Trie* xorTrie = new Trie(0);
int xorp[100005];

string numToBinaryString(int num) {
	string s;
	for (int bit = 20; bit >= 0; bit--)
		s += '0' + (!!(num & (1 << bit)));
	return s;
}

int main() {
	int n;
	in >> n;
	{
		string zeroStr = numToBinaryString(0);
		xorTrie->add(zeroStr.c_str(), 0);
	}
	int maxx = 0, l = 0, r = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		in >> x;
		xorp[i] = xorp[i - 1] ^ x;
		string invXorStr = numToBinaryString(~xorp[i]);
		Trie* best = xorTrie->findClose(invXorStr.c_str());
		if ((xorp[i] ^ xorp[best->getVal()]) > maxx) {
			maxx = xorp[i] ^ xorp[best->getVal()];
			l = best->getVal() + 1;
			r = i;
		}
		else if ((xorp[i] ^ xorp[best->getVal()]) == maxx && (i - best->getVal()) < (l - r + 1)) {
			l = best->getVal() + 1;
			r = i;
		}
		string xorStr = numToBinaryString(xorp[i]);
		xorTrie->add(xorStr.c_str(), i);
	}
	out << maxx << ' ' << l << ' ' << r << '\n';
}