Cod sursa(job #2277003)

Utilizator BRIOI19Ben Test BRIOI19 Data 5 noiembrie 2018 18:19:05
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
using namespace std;
struct node{
	node *arr[2];
	int val;
	int ind;
};
node *newnode(){
	node *temp = new node;
	temp->val = 0;
	temp->arr[0] = temp->arr[1] = NULL;
	temp->ind = -1;
	return temp;
}
void insert(node *root,int prexor,int index){
	node *temp = root;
	for(int i=31;i>=0;i--){
		bool val = prexor & (1<<i);

		if(temp->arr[val] == NULL){
			temp->arr[val] = newnode();
		}
		temp = temp->arr[val];
	}
	temp->val = prexor;
    temp->ind = index;
}

pair<int,int> query(node *root,int prexor){
	node *temp = root;
	for(int i=31;i>=0;i--){
		bool val = prexor & (1<<i);

		if(temp->arr[1-val] !=NULL){
			temp = temp->arr[1-val];
			//std::cout<<1<<endl;
		}
		else if(temp->arr[val] != NULL){
			temp = temp->arr[val];
			//std::cout<<0<<endl;
		}
	}	
	return make_pair(temp->ind,prexor^(temp->val));
}
int main(){
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
	int n;
	fin>>n;
	int arr[n+1];
	node *root = newnode();
	int ans = -1;
	int prexor = 0;
	int l,r = -1;
	for(int i=0;i<n;i++){
		fin>>arr[i];
		prexor = prexor^arr[i];
		
		insert(root,prexor,i+1);
		auto tempans = query(root,prexor);
		
		if(tempans.second>ans){
		    ans = tempans.second;
		    l = tempans.first+1;
		    r = i+1;
		}
	
	}
	fout<<ans<<" "<<l<<" "<<r<<endl;
	

}