In this HackerEarth Xor and Insert problem solution At first, you have a set S = 0 (it contains a zero). There are three types of queries:
  1. - 1 x: Add x to the set.
  2. - 2 x: For each element like y set y = y xor x.
  3. - 3: Print the minimum of the set.


HackerEarth Xor and Insert problem solution


HackerEarth Xor and Insert problem solution.

#include <bits/stdc++.h>
typedef long double ld;
using namespace std;
const int lg = 30, maxt = 5e5 * lg;
int q, t[maxt][2], sz = 1;
void insert(int x){
int p = 0;
for(int i = lg - 1; i >= 0; i--){
if(!t[p][x >> i & 1])
t[p][x >> i & 1] = sz++;
p = t[p][x >> i & 1];
}
}
int get(int x){
int ans = 0, p = 0;
for(int i = lg - 1; i >= 0; i--){
bool me = (x >> i & 1);
if(t[p][me])
p = t[p][me];
else
p = t[p][!me], ans |= 1 << i;
}
return ans;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
insert(0);
cin >> q;
int curx = 0;
while(q--){
int t;
cin >> t;
if(t == 1){
int x;
cin >> x;
insert(x ^ curx);
}
else if(t == 2){
int x;
cin >> x;
curx ^= x;
}
else
cout << get(curx) << '\n';
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define sz(x) ((int)x.size())
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define pb emplace_back
#define IINF 0x3f3f3f3f
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

inline int in() {int x, y; y = scanf("%d", &x); return x;}

const int N = 5e5 * 30;

int tree[N][2], cnt = 2;

int search(int x) {
int ans = 0, now = 1;
for(int i = 30; i >= 0; i--) {
bool j = (x>>i) % 2;
if(tree[now][j] == 0) {
ans += (1<<i);
}
if(tree[now][j] != 0)
now = tree[now][j];
else
now = tree[now][1 - j];
}
return ans;
}

void add(int x) {
int now = 1;
for(int i = 30; i >= 0 and now; i--) {
bool j = (x>>i) % 2;
if(tree[now][j] == 0)
tree[now][j] = cnt++;
now = tree[now][j];
}
}

int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int q, core = 0;
cin >> q;
add(0);
while(q--) {
int t, x;
cin >> t;
if(t == 3) {
cout << search(core) << endl;
continue;
}
cin >> x;
if(t == 1)
add(x ^ core);
else
core ^= x;
}
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}