C++ BEATS 100 %
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nstatic const auto init = []{\n    cin.tie(nullptr);\n    ios::sync_with_stdio(false);\n    return false;\n}();\nint prefsum[100005];\nint psz = 0;\n\nclass Solution {\npublic:\n    Solution(int n, vector<int>& blacklist) {\n        ::sort(begin(blacklist), end(blacklist));\n        psz = 0;\n        int pre = 0;\n        int sz = blacklist.size();\n        for (int i = 0; i < sz;) {\n            int j = i+1;\n            while (j < sz && blacklist[j] == blacklist[j-1] + 1) {++j;}\n            if (blacklist[i] != 0) {\n                intv.push_back({pre, blacklist[i]-1});\n            }\n            pre = blacklist[j-1] + 1;\n            i = j;\n        }\n        if (pre <= n-1) {\n            intv.push_back({pre, n-1});\n        }\n        total = 0;\n        for (int i = 0; i < intv.size(); ++i) {\n            int length = intv[i].second - intv[i].first + 1;\n            prefsum[psz++] = total;\n            total += length;\n        }\n    }\n    int pick() {\n        int r = rand()%total;\n        int idx = upper_bound(prefsum, prefsum+psz, r) - prefsum - 1;\n        int offset = r - prefsum[idx];\n        return intv[idx].first + offset;\n    }\n    vector<pair<int,int>> intv;\n    int total;\n};\n```
['C++']