Cod sursa(job #2888291)

Utilizator lolismekAlex Jerpelea lolismek Data 10 aprilie 2022 21:53:08
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int SIGMA = 2;

struct trie{
	int cnt, nr;
	trie *nxt[SIGMA];

	trie(){
		cnt = 0, nr = 0;
		for(int i = 0; i < SIGMA; i++)
			nxt[i] = 0;
	}
};

trie *root = new trie;

void insert_trie(trie *nod, int x){
	if(x == 0){
		nod -> cnt++;
		return;
	}

	int ind = !(x & 1);
	if(nod -> nxt[ind] == 0){
		nod -> nxt[ind] = new trie;
		nod -> nr++;
	}

	insert_trie(nod -> nxt[ind], x >> 1);
}

int match_trie(trie *nod, int x, int match){
	if(x == 0)
		return match;

	int ind = !(x & 1);
	if(nod -> nxt[ind])
		match_trie(nod -> nxt[ind], x >>= 1, ((match ^ ind) << 1));
	else
		match_trie(nod -> nxt[1 - ind], x >>= 1, ((match ^ (1 - ind)) << 1));
}

int main(){
	int n, xor_sum = 0, ans = -1;
	fin >> n;
	for(int i = 1; i <= n; i++){
		int x;
		fin >> x, xor_sum ^= x;

		int reverse = 0, xc = xor_sum;
		while(xc){
			if(xc & 1)
				reverse ^= 1;
			reverse <<= 1;
		}

		int match = match_trie(root, reverse, 0);

		ans = max( ans, (xor_sum ^ match) );

		insert_trie(root, reverse);
	}

	fout << ans;
	return 0;
}