C++ O(B)/O(1), beats 95%, uses whitelist when B>N/2
Make blackset in O(B), then\n1. B<=N/2, uses rejection sampling. O(1) average per sample because the probability of rejection is at most 1/2.\n2. B>N/2, make wh
Make blackset in `O(B)`, then\n1. `B<=N/2`, uses rejection sampling. `O(1)` average per sample because the probability of rejection is at most 1/2.\n2. `B>N/2`, make whitelist in `O(N)` (which equals `O(B)` since `N/B` is bounded by a constant factor 2), and sample from whitelist.\n```\nclass Solution {\n    int n;\n    vector<int> whitelist;\n    unordered_set<int> blackset;\npublic:\n    Solution(int N, vector<int> blacklist) {\n        n=N;\n        blackset=unordered_set<int>(blacklist.begin(),blacklist.end());\n        whitelist=vector<int>();\n        if(blacklist.size()>N/2)\n            for(int i=0;i<N;i++)\n                if(!blackset.count(i))whitelist.push_back(i);\n    }\n    \n    int pick() {\n        if(!whitelist.empty())return whitelist[rand()%whitelist.size()];\n        else while(true){\n            int r=rand()%n;\n            if(!blackset.count(r))return r;\n        }\n    }\n};\n```
[]