Cod sursa(job #1981621)

Utilizator brczBereczki Norbert Cristian brcz Data 16 mai 2017 11:57:47
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 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;

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


struct Node{

	int idx;
	Node* sons[2];
};


class BinTrie{
private:
	Node *root;
	int queryIdx = 0;

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


		if(level == -1){
			this->queryIdx = curr->idx;
			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,int i){

		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();
		
		curr->sons[bit]->idx = i;
		insert(level-1,x,curr->sons[bit],i);
	}

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

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

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

	int getQueryIdx(){
		return this->queryIdx;
	}

};

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{};

	fin >> n;
	int xorSoFar = 0;
	int xorMax = 0;
	int begMax = -1,endMax = 100003;



	for(int i=0;i<n;i++){
		fin >> x;
		xorSoFar^=x;
		trie.insertTrie(xorSoFar,i);
		int q = trie.queryTrie(xorSoFar);


		if(xorMax < q){
			xorMax = q;
			begMax = trie.getQueryIdx();
			endMax = i;
		}
		if(xorMax == q && i-trie.getQueryIdx() < endMax-begMax){
			begMax = trie.getQueryIdx();
			endMax = i;	
		}

		if(xorMax <= x){
			xorMax = x;
			begMax = i;
			endMax = i;
		}
	}


	fout << xorMax << ' ' << begMax+2 << ' ' << endMax+1 << '\n';

	return 0;
}