HackerEarth Xor and Insert problem solution

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 x: Add x to the set.
– 2 x: For each element like y set y = y xor x.
– 3: Print the minimum of the set.

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 << "msn";
    return 0;
}

coding problems solutions