Cod sursa(job #3210880)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 7 martie 2024 16:35:58
Problema Xor Max Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.88 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream in("xormax.in");
ofstream out("xormax.out");
#define cin in
#define cout out
#endif // LOCAL

struct Trie {
	struct TrieNod {
		int pozitie, valoare;
		TrieNod* fiu[2];

		TrieNod() {
			pozitie = -1; valoare = -1;
			fiu[0] = fiu[1] = nullptr;
		}
	};

	TrieNod* radacina = nullptr;

	TrieNod* _insert(TrieNod* cap, int numar, int bit_index, int poz) {
		if(cap == nullptr) {
			cap = new TrieNod();
		}

		if(bit_index == -1) { // am ajuns la finalul numarului, deci punem nodul cu 
			// pozitia poz care trebuie retinuta
			cap->pozitie = poz;
			cap->valoare = numar;
			return cap; 
		}

		int bit_curent = (numar >> bit_index) & 1;

		if(bit_curent == 1) {
			// iteram recursiv pe dreapta (fiul '1')
			cap->fiu[1] = _insert(cap->fiu[1], numar, bit_index - 1, poz);
		}
		else {
			// iteram recursiv pe stanga (fiul '0')
			cap->fiu[0] = _insert(cap->fiu[0], numar, bit_index - 1, poz);
		}

		// cap->fiu[bit_curent] = _insert(cap->fiu[bit_curent], numar, bit_index - 1, poz);
	
		return cap;
	}

	void add(int numar, int pozitie) {
		// _insert este o functie ajutatoare ce ea o trie, alaturi de nivelul ei, si insereaza
		// in tria respectiva cat trebuie din numarul dat, retinand in ultimul nod pozitia

		// _insert returneaza nodul triei, in caz ca trebuie creat unul nou!

		radacina = _insert(radacina, numar, 23, pozitie); 
	}

	pair<int, int> _cauta(TrieNod* cap, int numar, int bit_index) {
		if(bit_index == -1) { // daca am ajuns intr-o frunza a triei
			return {cap->valoare ^ numar, cap->pozitie};
		}

		int bit_curent = (numar >> bit_index) & 1;

		// fiindca cautam xorul maxim, incercam sa mergem pe partea opusa a bitului curent

		if(bit_curent == 0) {
			if(cap->fiu[1] != nullptr) {
				return _cauta(cap->fiu[1], numar, bit_index - 1);
			}
			else {
				return _cauta(cap->fiu[0], numar, bit_index - 1);
			}
		}
		else {
			if(cap->fiu[0] != nullptr) {
				return _cauta(cap->fiu[0], numar, bit_index - 1);
			}
			else {
				return _cauta(cap->fiu[1], numar, bit_index - 1);
			}
		}

		/*
		// varianta mai scurta
		if(cap->fiu[1 - bit_curent] != nullptr) return _cauta(cap->fiu[1 - bit_curent], numar, bit_index - 1);
		else return _cauta(cap->fiu[bit_curent], numar, bit_index - 1);
		*/

		return {-1, -1}; // acest caz nu ar trebui sa se intample!
	}

	pair<int, int> find_xor_max(int numar) {
		// _cauta este o functie ajutatoare care itereaza in trie dupa cum ne zice numarul
		// si returneaza maximul obtinut din xorul lui numar cu orice numar din trie, alaturi de pozitia partenerului

		return _cauta(radacina, numar, 23);
	}
};

pair<int, pair<int, int>> my_max(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
	if(a.first != b.first) return a.first > b.first ? a : b;
	if(a.second.first != b.second.first) return a.second.first < b.second.first ? a : b;
	return a.second.second < b.second.second ? a : b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n; cin >> n;
	vector<int> v(n); for(auto &x : v) cin >> x;
	
	vector<int> xorpartial = {0};
	for(auto e : v) {
		xorpartial.push_back(xorpartial.back() ^ e);
	}
	// acum, vrem sa gasim i si j a.i. xorpartial[i] ^ xorpartial[j] sa fie maxim

	// Trie.add(int numar, int poz) -> adauga numarul in trie retinand ca vine de la pozitia poz
	// pair<int, int> Trie.find_xor_max(int numar) -> returneaza maximul obtinut din xorul lui numar cu orice numar din trie, alaturi de pozitia partenerului

	Trie trie;
	
	pair<int, pair<int, int>> best = {0, {1, 1}};

	trie.add(xorpartial[0], 0);

	for(int i = 1; i < xorpartial.size(); i++) {
		auto rasp_trie = trie.find_xor_max(xorpartial[i]);
		pair<int, pair<int, int>> current;
		current.first = rasp_trie.first;
		current.second = {rasp_trie.second, i};
	
		best = my_max(best, current);

		trie.add(xorpartial[i], i);
	}

	cout << best.first << ' ' << best.second.first + 1 << ' ' << best.second.second << '\n';
}