1
class Solution {
2
 public:
3
  int idx;
4
  unordered_map<int, int> mp;
5
  set<int> s;
6
  Solution(int n, vector<int> &blacklist) {
7
    idx = n - blacklist.size();
8
    n--;
9
    for (int i = 0; i < blacklist.size(); i++) s.insert(blacklist[i]);
10
    for (int i = 0; i < blacklist.size(); i++) {
11
      if (blacklist[i] < idx) {
12
        while (s.find(n) != s.end()) n--;
13
        mp[blacklist[i]] = n;
14
        n--;
15
      }
16
    }
17
  }
18

19
  int pick() {
20
    int ans = rand() % (idx);
21
    if (mp.count(ans)) return mp[ans];
22
    return ans;
23
  }
24
};