Cod sursa(job #2909410)

Utilizator lolismekAlex Jerpelea lolismek Data 13 iunie 2022 13:57:22
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

const int SIGMA = 2, P = 21;

struct trie{
	int poz;
	trie *nxt[SIGMA];
};

trie *root = new trie;

void insertTrie(trie *nod, int val, int bit, int i){
	if(bit < 0){
		nod -> poz = i;
		return;
	}

	int ind = (val >> bit);
	if(nod -> nxt[ind] == NULL)
		nod -> nxt[ind] = new trie();


	insertTrie(nod -> nxt[ind], val & ((1 << bit) - 1), bit - 1, i);
}

 int findTrie(trie *nod, int val, int bit, int ans){
 	if(bit < 0)
 		return ans;
 	
 	int ind = !(val >> bit);

 	if(nod -> nxt[ind] != NULL)
 		return findTrie(nod -> nxt[ind], val & ((1 << bit) - 1), bit - 1, ans * 2 + 1);
 	else if(nod -> nxt[!ind] != NULL)
 		return findTrie(nod -> nxt[!ind], val & ((1 << bit) - 1), bit - 1, ans * 2 + 0);
 	else
 		return ans;
 	
 }

int main(){
	
	int n, Xsum = 0, maxi = 0;
	fin >> n;
	insertTrie(root, 0, P, 0);

	for(int i = 1; i <= n; i++){
		int x;
		fin >> x;
		Xsum ^= x;

		int tmp = findTrie(root, Xsum, P, 0);

		maxi = max(maxi, tmp);

		insertTrie(root, Xsum, P, i);
	}

	fout << maxi << '\n';

	return 0;
}