Skip to content

Instantly share code, notes, and snippets.

@harshraj22
Last active June 28, 2019 06:46
Show Gist options
  • Save harshraj22/9fd31fd7ff166fa0c0035fddfdf248a9 to your computer and use it in GitHub Desktop.
Save harshraj22/9fd31fd7ff166fa0c0035fddfdf248a9 to your computer and use it in GitHub Desktop.
To discuss about 'xor and insert' problem on HackerEarth
#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;
}

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.

// 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;
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment