题解：CF2146C Wrong Binary Search

沉石鱼惊旋 · 2025-09-25 14:50:16 · 题解

手摸这个过程，或者瞪眼发现，一个数能被查到，当且仅当前面的都比它小，后面的都比它大。

那么一个简单的构造是：我们在 \texttt{1} 的位置填原数，对于连续的 \tt{0}，我们构造错排即可。

构造错排太难了，我不会（x

注意到随机排列是错排的概率是 \frac{1}{\mathrm{e}}，故我们对这个连续的 \texttt{0} 的小区间随机一个排列，检查是否是错排，期望常数次就可以随机出来。

cpp 提交记录：https://codeforces.com/contest/2146/submission/339811035

py 提交记录：https://codeforces.com/contest/2146/submission/339811052