Cod sursa(job #2891384)

Utilizator Langa_bLanga Radu Langa_b Data 18 aprilie 2022 15:03:40
Problema Xor Max Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n, sm[100002];
struct trie {
	int cnt, nrfii;
	trie* bit[2];
	trie() {
		cnt = 0;
		nrfii = 0;
		bit[0] = NULL;
		bit[1] = NULL;
	}
};
trie* T = new trie;
int nr, indice;
void add(trie* act, int ind) {
	if (ind == -1) {
		act->cnt = indice;
		return;
	}
	int bit = (1 << ind);
	if ((nr & bit) == 0) {
		if (act->bit[0] == NULL) {
			act->bit[0] = new trie;
		}
		add(act->bit[0], ind - 1);
	}
	else {
		if (act->bit[1] == NULL) {
			act->bit[1] = new trie;
		}
		add(act->bit[1], ind - 1);
	}
}
int ans, ansi, cmp, st, fin, dif, alt;
void prc(trie* act, int ind) {
	if (ind == -1) {
		alt = act->cnt;
		return;
	}
	int bit = (1 << ind);
	dif = 0;
	if ((cmp & bit) != 0) {
		dif = 1;
	}
	if (act->bit[1 - dif] != NULL) {
		ansi = (ansi | bit);
		prc(act->bit[1 - dif], ind - 1);
	}
	else if (act->bit[dif] != NULL) {
		prc(act->bit[dif], ind - 1);
	}
}
int main() {
	cin >> n;
	int x;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		sm[i] = sm[i - 1] ^ x;
	}
	for (int i = 0; i <= n; i++) {
		indice = i;
		nr = sm[i];
		add(T, 20);
	}
	for (int i = 1; i <= n; i++) {
		ansi = 0;
		cmp = sm[i];
		prc(T, 20);
		if (ans < ansi) {
			ans = ansi;
			st = min(i, alt) + 1;
			fin = max(i, alt);
		}
	}
	cout << ans << ' ' << st << ' ' << fin;
}