Cod sursa(job #2660739)

Utilizator mircearoataMircea Roata Palade mircearoata Data 20 octombrie 2020 13:19:02
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 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];

int main() {
	int n;
	in >> n;
	xorTrie->add("00000000000000000000000", -1);
	int maxx = 0, l = 0, r = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		in >> x;
		xorp[i] = xorp[i - 1] ^ x;
		char invXorString[25];
		for (int bit = 20; bit >= 0; bit--)
			invXorString[20 - bit] = '0' + (!(xorp[i] & (1 << bit)));
		invXorString[21] = '\0';
		Trie* best = xorTrie->findClose(invXorString);
		if ((xorp[i] ^ xorp[best->getVal()]) > maxx) {
			maxx = xorp[i] ^ xorp[best->getVal()];
			l = best->getVal() + 1;
			r = i;
		}
		char xorString[25];
		for (int bit = 20; bit >= 0; bit--)
			xorString[20 - bit] = '0' + (!!(xorp[i] & (1 << bit)));
		xorString[21] = '\0';
		xorTrie->add(xorString, i);
	}
	out << maxx << ' ' << l << ' ' << r;
}