Cod sursa(job #2891403)

Utilizator Langa_bLanga Radu Langa_b Data 18 aprilie 2022 15:53:46
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n;
struct trie {
	int cnt;
	trie* bit[2];
	trie() {
		cnt = 0;
		bit[0] = NULL;
		bit[1] = NULL;
	}
};
trie* T = new trie;
void add(trie* act, int ind, int indice, int nr) {
	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, indice, nr);
	}
	else {
		if (act->bit[1] == NULL) {
			act->bit[1] = new trie;
		}
		add(act->bit[1], ind - 1, indice, nr);
	}
}
int ans, ansi, cmp, st, fin, alt, dif;
void prc(trie* act, int ind, int cmp) {
	if (ind == -1) {
		alt = act->cnt;
		return;
	}
	int bit = (1 << ind);
	if ((cmp & bit) != 0) {
		dif = 1;
	}
	else {
		dif = 0;
	}
	if (act->bit[1 - dif] != NULL) {
		ansi = (ansi | bit);
		prc(act->bit[1 - dif], ind - 1, cmp);
	}
	else if (act->bit[dif] != NULL) {
		prc(act->bit[dif], ind - 1, cmp);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int x;
	add(T, 22, 0, 0);
	int sp = 0;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		sp = sp ^ x;
		ansi = 0;
		prc(T, 22, sp);
		if (ans < ansi) {
			ans = ansi;
			st = alt + 1;
			fin = i;
		}
		add(T, 22, i, sp);
	}
	cout << ans << ' ' << st << ' ' << fin;
}