Cod sursa(job #1423751)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 22 aprilie 2015 16:07:24
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <utility>
#include <tuple>
using namespace std;

struct trie_nod{
	~trie_nod(){
		delete copii[0];
		delete copii[1]; }
	trie_nod* copii[2] = {nullptr, nullptr};
	int val = 0; };

constexpr int sz = 21;

void adauga(trie_nod* t, const int n, const int val){
	bool bit;
	for(int adanc = sz; adanc >= 0; --adanc){
		bit = (n & (1<<adanc))>>adanc;
		if(t->copii[bit] == nullptr){
			t->copii[bit] = new trie_nod; }
		t = t->copii[bit]; }
	t->val = val; }

tuple<int, int> cauta(trie_nod* t, const int n){
	int rez = 0;
	bool bit;
	for(int adanc = sz, bit; adanc >= 0; --adanc){
		bit = (n & (1<<adanc))>>adanc;
		if(t->copii[bit] != nullptr){
			t = t->copii[bit];
			rez *= 2;
			rez += bit; }
		else{
			t = t->copii[!bit];
			rez *= 2;
			rez += !bit; } }
	return make_tuple(rez, t->val); }

int main(){
	ifstream f("xormax.in");
	int n = 0;
	f >> n;
	trie_nod* radacina = new trie_nod;
	adauga(radacina, 0, 0);
	int st_max = 0, dr_max = 0, val_max = -1, st_cur, val_cur;
	for(int i = 0, x = 0, suma_partiala = 0; i < n; ++i){
		f >> x;
		suma_partiala ^= x;
		adauga(radacina, suma_partiala, i+1);
		tie(val_cur, st_cur) = cauta(radacina, ~suma_partiala);
		val_cur ^= suma_partiala;
		if(val_cur > val_max){
			val_max = val_cur;
			st_max = st_cur;
			dr_max = i; }
		else if(val_cur == val_max && i-st_cur < dr_max-st_max){
			val_max = val_cur;
			st_max = st_cur;
			dr_max = i; } }
	ofstream g("xormax.out");
	g << val_max << ' ' << st_max+1 << ' ' << dr_max+1;
	return 0; }