Submission #37363836

---

Source Code Expand

/*
 * File created on 12/17/2022 at 16:57:52.
 * Link to problem: 
 * Description: 
 * Time complexity: O()
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2022 Francois Vogel
*/

#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 pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define sz(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define int ll
#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int LOG = 31;

struct Node {
    Node() {
        c = new Node* [2];
        c[0] = c[1] = nullptr;
    }
    void upd(int x, int h = LOG) {
        if (h == -1) return;
        if ((x>>h)&(int)(1)) {
            if (c[1] == nullptr) c[1] = new Node();
            c[1]->upd(x, h-1);
        } else {
            if (c[0] == nullptr) c[0] = new Node();
            c[0]->upd(x, h-1);
        }
    }
    int dp(int h = LOG) {
        if (h == -1) return 0;
        if (c[0] == nullptr) return c[1]->dp(h-1);
        if (c[1] == nullptr) return c[0]->dp(h-1);
        int sA = c[0]->dp(h-1);
        int sB = c[1]->dp(h-1);
        return min(sA, sB) + (1<<h);
    }
    Node** c;
};

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    Node* root = new Node();
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        root->upd(x);
    }
    cout << root->dp();

    cout.flush();
    int d = 0;
    d++;
}

Submission Info

Judge Result