Cod sursa(job #2521947)

Utilizator AlexNeaguAlexandru AlexNeagu Data 11 ianuarie 2020 18:59:19
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
int mx = - 1000000000;
int start = 0, finish = 0;
struct Trie {
	Trie *bits[2];
	int key;
	Trie() {
		key = 0;
		bits[1] = NULL;
		bits[0] = NULL;
	}
};
Trie *root = new Trie();
void upd(int sum, int bit, Trie *node, int pos) {
	int upd_bit;
	if (bit == -1) {
		// cout << "\n";
		node -> key = pos;
		return;
	}
	if ((1 << bit) & sum) upd_bit = 1; else upd_bit = 0;
	// cout << upd_bit << " ";
	if (node -> bits[upd_bit] == NULL) {
		node -> bits[upd_bit] = new Trie();
	}
	upd(sum, bit - 1, node -> bits[upd_bit], pos);
}
pair < int, int > q(int bit, int sum, int ans, Trie *node) {
	if (bit == -1) {
		return make_pair(ans, node -> key + 1);
	}
	int upd_bit;
	if ((1 << bit) & sum) upd_bit = 1; else upd_bit = 0;
	if (node -> bits[!upd_bit] != NULL) {
		return q(bit - 1, sum , ans + (1 << bit), node -> bits[!upd_bit]);
	}
	return q(bit - 1, sum, ans , node -> bits[upd_bit]);
}
int main() {
	int sum_x = 0;
	int n;
	in >> n;
	for (int i = 1; i <= n; i++) {
		int x; in >> x;
		sum_x ^= x;
		upd(sum_x, 22, root, i);
		pair < int, int > bst_res = q(22, sum_x, 0, root);
		if (mx < bst_res.first) {
			mx = bst_res.first;
			start = bst_res.second;
			finish = i;
		}
	}
	out << mx << " " << start << " " << finish << "\n";
	return 0;
}