CF2146C Wrong Binary Search

给定一个整数 $n$ 和一个长度为 $n$ 的二进制字符串 $s$。 对于长度为 $n$ 的排列 $p$ 和整数 $x$，我们按照如下伪代码定义 $\text{find}(x)$： ``` function find(int x): l := 1 r := n while l x: r := m - 1 else: l := m + 1 return undefined // not found ``` 我们称整数 $x$（$1 \le x \le n$）是 稳定 的，当且仅当无论在上述伪代码中每次如何选择 $m$，$\text{find}(x)$ 总是不为 undefined 且始终有 $p_{\text{find}(x)}=x$ 成立。 你需要构造一个长度为 $n$ 的排列 $p$，使得： - 对于每个 $1 \le i \le n$，当且仅当 $s_i=\mathtt{1}$ 时，整数 $i$ 是稳定的。 或者判断不存在这样的排列。 $^{\text{∗}}$ 二进制字符串是指仅包含字符 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。 $^{\text{†}}$ 长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数组成的序列。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但出现了 $4$）。

每个测试点包含若干测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。测试用例的描述如下。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2\cdot 10^5$），表示排列的长度。 第二行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i=\mathtt{0}$ 或 $s_i=\mathtt{1}$）。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例： - 如果不存在这样的排列，输出一行 "NO"。 - 否则，第一行输出 "YES"。然后在第二行输出 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$（$1\le p_i\le n$），表示你构造的排列。 输出中的单词大小写不敏感。例如，"yEs"、"yes"、"Yes"、"YES" 都被认为是肯定的输出。 如果有多组满足条件的答案，可以输出任意一种。

在第一个测试用例中，可以构造 $p=[1,2,3]$。以 $\text{find(2)}$ 为例： - 首先，$l=1$，$r=3$； - 随机选择 $l=1$ 到 $r=3$ 之间的 $m$。 - 如果选择 $m=1$： - $p_1=12$，$r$ 更新为 $m-1=2$，此时 $l=2$，$r=2$，只能选择 $m=2$，$p_2=2$，返回 $2$。 - 如果选择 $m=2$： - $p_2=2$，直接返回 $2$。 - 如果选择 $m=3$，过程与 $m=1$ 类似，最终总是返回 $2$。 - 所以，无论过程中如何选择 $m$，$\text{find}(2)$ 的返回值始终是 $2$。 因此，$p_{\text{find}(2)}=p_2=2$ 始终成立，整数 $2$ 是稳定的。 同理，可以证明 $1$ 和 $3$ 也是稳定的。因此，$p = [1,2,3]$ 是一个合法答案。 在第二个测试用例中，可以构造 $p=[2,4,3,5,1]$。以 $\text{find}(3)$ 为例： - 首先，$l=1,r=5$； - 随机选择 $l=1$ 到 $r=5$ 的 $m$，假设选择 $m=2$； - $p_2=4>3$，所以 $r$ 变为 $m-1=1$，此时 $l=1,r=1$； - 随机选择 $l=1$ 到 $r=1$ 的 $m$，只能选 $m=1$； - $p_1=2r$，循环结束，返回 undefined。 所以，$\text{find}(3)$ 的返回值为 undefined，整数 $3$ 不是稳定的。 同理可以分析 $1$，$2$，$4$，$5$ 也都不是稳定的。因此，$p = [2,4,3,5,1]$ 是一个合法解。 其它排列比如 $[5,4,3,2,1]$，$[3,5,1,4,2]$ 也都是合法的答案，你可以输出任何一个。 在第三个测试用例中，可以证明不存在这样的排列。 由 ChatGPT 5 翻译