1895D - XOR Construction - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
struct node{
    node* next[2];
    int end;
    node(){
        end=0;
        next[0]=nullptr;
        next[1]=nullptr;
    }
};

struct trie{
    node* root;
    trie(){
        root=nullptr;
    }
    trie(vector<int> inp){
        root=new node();
        for(int i=0;i<inp.size();i++){
            node* curr=root;
            for(int j=30;j>=0;j--){
                if(((inp[i]>>j)&1)==1){
                    if(curr->next[1]==nullptr){
                        curr->next[1]=new node();
                    }
                    curr=curr->next[1];
                }
                else{
                    if(curr->next[0]==nullptr){
                        curr->next[0]=new node();
                    }
                    curr=curr->next[0];
                }
            }
            curr->end++;
        }
    }
    int find(int x){
        int ans=0;
        node* curr=root;
        for(int i=30;i>=0;i--){
            if(curr->next[((x>>i)&1)^1]!=nullptr){
                ans+=(1<<i);
                curr=curr->next[((x>>i)&1)^1];
            }
            else{
                curr=curr->next[((x>>i)&1)];
            }
        }
        return ans;
    }
};
void solve(){
    int n; cin>>n;
    vector<int> a(n-1);
    for(int i=0;i<n-1;i++) cin>>a[i];
    for(int i=1;i<n-1;i++){
        a[i]^=a[i-1];
    }
    trie t(a);
    int start=-1;
    for(int i=0;i<n;i++){
        if(t.find(i)<n){
            start=i;
            break;
        }
    }
    cout<<start<<" ";
    for(int i=0;i<n-1;i++){
        cout<<(start^a[i])<<" ";
    }cout<<'\n';
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int tt=1;
    // cin>>tt;

    while(tt--) solve();
    return 0;
}
/*
1. Check borderline constraints. Can a variable you are dividing by be 0?
2. Use ll while using bitshifts
3. Do not erase from set while iterating it
4. Initialise everything
5. Read the task carefully, is something unique, sorted, adjacent, guaranteed??
6. DO NOT use if(!mp[x]) if you want to iterate the map later
7. Are you using i in all loops? Are the i's conflicting?
8. Use iterator to iterate thorugh maps if you want to changes the values
9. Use vector in place of pair to speed up typing
10. Try to make function outside all the loops in open space in order to reduce numerous compiling
11. Try not  use to INT_MAX because of out of bounds issues
*/