To discuss about 'xor and insert' problem on HackerEarth

accepted_solution.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

struct trie{
	ll num=0;
	trie* lk[2]={nullptr};

};

trie* root=nullptr;

trie* get(){
	trie* temp =new trie;
	temp->num=0;
	temp->lk[0]=temp->lk[1]=nullptr;
	return temp;
}

void add(ll n){
	if(root==nullptr)root=get();
	trie* node=root;
	for(ll i=32;i>=0;i--){
		ll val=(n & 1LL<<i)?1:0;
		if(node->lk[val]==nullptr)
			node->lk[val]=get();
		node=node->lk[val];
	}
	node->num=n;
}

ll search(ll n){
	if(root==nullptr || n==0)return 0;
	trie* node=root;
	for(ll i=32;i>=0;i--){
		ll val=(n & 1LL<<i)?1:0;
		if(node->lk[val]==nullptr)
			node=node->lk[1-val];
		else node=node->lk[val];
	}
	return node->num;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	ll i,j,k,n,m=0;
	cin>>n;	add(0); //if we don't add(0) it gives wrong answer
	while(n--){
		cin>>j;
		if(j==3)cout<<(m^search(m))<<"\n";
		else cin>>k;

		if(j==1)add(k^m);
		else if(j==2)m^=k;
	}

	return 0;
}

Logic.md

used the same logic described here.I wonder why there is so much diffrence when array of fixed size is used instead of unordered_map. Also, why the later solution gives TLE as well.

Other_rejected_solution.cpp

// https://codeforces.com/blog/entry/60737

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int

typedef cc_hash_table<ll,ll,hash<ll> >lk;
 
struct _trie_{
	// bool end=false;
	ll num=0;
	// map<ll,_trie_* > lk;
	cc_hash_table<ll,_trie_* > lk;
 
};
_trie_* root=nullptr;
 
_trie_* get(){
	_trie_* temp =new _trie_;
	temp->num=0;
	return temp;
}
 
void add(ll n){
	if(root==nullptr)root=get();
	_trie_* node=root;
	for(ll i=32;i>=0;i--){
		ll val=(n & 1LL<<i)?1:0;
		if(node->lk.find(val)==node->lk.end())
			node->lk[val]=get();
		node=node->lk[val];
	}
	node->num=n;
}
 
ll search(ll n){
	if(root==nullptr || n==0)return 0;
	_trie_* node=root;
	for(ll i=32;i>=0;i--){
		ll val=(n & 1LL<<i)?1:0;
		if(node->lk.find(val)==node->lk.end())
			node=node->lk[1-val];
		else node=node->lk[val];
	}
	return node->num;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	ll i,j,k,n,m=0;
	cin>>n;	add(0);
	while(n--){
		cin>>j;
		if(j==3)cout<<(m^search(m))<<"\n";
		else cin>>k;
 
		if(j==1)add(k^m);
		else if(j==2)m^=k;
	}
 
	return 0;
}

TLE_and_MLE_solution.cpp

#include<bits/stdc++.h>
using namespace std;
 
struct trie{
	int num=0;
	map<int,trie* > lk;
 
};
trie* root=nullptr;
 
trie* get(){
	trie* temp =new trie;
	temp->num=0;
	return temp;
}
 
void add(int n){
	if(root==nullptr)root=get();
	trie* node=root;
	for(int i=32;i>=0;i--){
		int val=(n & 1LL<<i)?1:0;
		if(node->lk.find(val)==node->lk.end())
			node->lk[val]=get();
		node=node->lk[val];
	}
	node->num=n;
}
 
int search(int n){
	if(root==nullptr || n==0)return 0;
	trie* node=root;
	for(int i=32;i>=0;i--){
		int val=(n & 1LL<<i)?1:0;
		if(node->lk.find(val)==node->lk.end())
			node=node->lk[1-val];
		else node=node->lk[val];
	}
	return node->num;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	int i,j,k,n,m=0;
	cin>>n;	add(0);
	while(n--){
		cin>>j;
		if(j==3)cout<<(m^search(m))<<"\n";
		else cin>>k;
 
		if(j==1)add(k^m);
		else if(j==2)m^=k;
	}
 
	return 0;
}