Cod sursa(job #1981610)

Utilizator brczBereczki Norbert Cristian brcz Data 16 mai 2017 11:09:05
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
#define bg begin
#define nd end
using namespace std;

#define int long long

const int maxn = 100003;
const int maxk = 1003;

int n;


struct Node{

	Node* sons[2];
};

class BinTrie{
private:
	Node *root;

	int query(int level,int x,Node* curr){

		if(level == -1) return 0;
		int bit = x & (1<<level);
		if(bit) bit = 1;
		else bit = 0;
		if(curr->sons[1-bit]==NULL){
			return query(level-1,x,curr->sons[bit]);
		}
		else{
			return (1 << level) + query(level-1,x,curr->sons[1-bit]);
		}
	}

	void insert(int level,int x,Node* curr){

		if(level == -1) return;

		int bit = x & (1 << level);
		if(bit) bit = 1;
		else bit = 0;

		if(curr->sons[bit] == NULL) curr->sons[bit] = new Node();
		
		insert(level-1,x,curr->sons[bit]);
	}

public:
	void insertTrie(int x){
		this->insert(21,x,root);
	}

	int queryTrie(int x){
		return this->query(21,x,root);
	}

	BinTrie(){
		root = new Node();
	}

};

int32_t main(){

	// #ifndef ONLINE_JUDGE
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	// #endif

	// ios_base::sync_with_stdio(false);

	int x;
	BinTrie trie{};

	cin >> n;
	int xorSoFar = 0;
	int xorMax = 0;


	for(int i=0;i<n;i++){
		cin >> x;
		xorSoFar^=x;
		trie.insertTrie(xorSoFar);
		xorMax = max(xorMax,max(x,trie.queryTrie(x)));
	}


	cout << xorMax << '\n';

	return 0;
}