solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

template <class T>
auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D>
auto vect(const T& v, int n, D... m) {
    return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}

template <typename T>
static constexpr T inf = numeric_limits<T>::max() / 2;
mt19937_64 mrand(random_device{}());
long long rnd(long long x) { return mrand() % x; }
int lg2(long long x) { return sizeof(long long) * 8 - 1 - __builtin_clzll(x); }

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

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


class Solution {
   public:
    vector<int> b;
    int n;
    Solution(int _n, vector<int>& blacklist) {
        sort(blacklist.begin(), blacklist.end());
        b = blacklist;
        b.push_back(_n);
        n = _n;
    }

    int pick() {
        int num = n - b.size() + 1;
        int idx = rnd(num) + 1;
        int l = 0, r = b.size() - 1;
        int ans = -1;
        while (l <= r) {
            int m = l + r >> 1;
            int val = b[m] - m;
            if (val >= idx) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        int val = b[ans] - ans - idx;
        return b[ans] - 1 - val;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(n, blacklist);
 * int param_1 = obj->pick();
 */