C. 错误二分查找

每次测试时间限制：$2$ 秒
每次测试内存限制：$256$ 兆字节

题目描述

给定一个整数 $n$ 和一个长度为 $n$ 的二进制字符串 $s$。

对于一个长度为 $n$ 的排列 $p$ 和一个整数 $x$，我们定义 $\text{find}(x)$ 的伪代码如下：

function find(int x):
    l := 1
    r := n
    while l <= r:
        let m be a random integer between l and r (inclusive)
        if p[m] == x:
            return m
        if p[m] > x:
            r := m - 1
        else:
            l := m + 1
    return undefined     // 未找到

我们称整数 $x$（$1 \le x \le n$）是稳定的，当且仅当无论 $\text{find}(x)$ 过程中如何随机选择 $m$，它总是返回一个确定的值（不是未定义），并且 $p[\text{find}(x)] = x$ 始终成立。

你必须构造一个长度为 $n$ 的排列 $p$，使得：

• 对于每个 $1 \le i \le n$，整数 $i$ 是稳定的当且仅当 $s_i = 1$。

或者判断这样的排列不存在。

注意：

• 二进制字符串是指每个字符为 $0$ 或 $1$ 的字符串。
• 长度为 $n$ 的排列是由 $n$ 个不同的整数 $1$ 到 $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 \in \{0,1\}$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例：

• 如果不存在这样的排列，则输出一行 "NO"。
• 否则，第一行输出 "YES"，第二行输出 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$），表示你构造的排列。

你可以以任意大小写输出答案（例如，"yEs"、"yes"、"Yes" 和 "YES" 均视为肯定答案）。

如果有多个答案，你可以输出任意一个。

示例

输入：

6
3
111
5
00000
5
10100
7
0010000
11
00001001100
12
011100010000

输出：

YES
1 2 3 
YES
2 4 3 5 1
NO
YES
2 1 3 5 7 6 4
YES
2 1 4 3 5 7 6 8 9 11 10
NO

注释

第一个测试用例：我们构造了 $p = [1,2,3]$。以 $\text{find}(2)$ 为例：

• 初始 $l = 1$，$r = 3$；
• 随机选择 $m$ 在 $[1,3]$ 之间：
  • 若 $m=1$：$p_1 = 1 < 2$，所以 $l = m+1 = 2$，此时 $l=2,r=3$；
    • 再随机选 $m$：
      • $m=2$：$p_2=2$，返回 $2$；
      • $m=3$：$p_3=3>2$，则 $r=m-1=2$，此时 $l=2,r=2$，只能选 $m=2$，$p_2=2$，返回 $2$。
  • 若 $m=2$：$p_2=2$，直接返回 $2$。
  • 若 $m=3$：$p_3=3>2$，则 $r=2$，此时 $l=1,r=2$；
    • 再选 $m$：
      • $m=1$：$p_1=1<2$，$l=2$，此时 $l=2,r=2$，只能选 $m=2$，返回 $2$；
      • $m=2$：$p_2=2$，返回 $2$。
• 总之，无论随机选择如何，$\text{find}(2)$ 总是返回 $2$，因此 $2$ 稳定。

同理可证 $1$ 和 $3$ 也稳定。因此 $p=[1,2,3]$ 是一个合法答案。

第二个测试用例：构造 $p = [2,4,3,5,1]$。以 $\text{find}(3)$ 为例：

• 初始 $l=1,r=5$；
• 若选 $m=2$：$p_2=4>3$，则 $r=m-1=1$，此时 $l=1,r=1$；
  • 只能选 $m=1$：$p_1=2<3$，则 $l=m+1=2$，此时 $l=2>r=1$，退出循环，返回未定义。
• 因此 $\text{find}(3)$ 可能返回未定义，故 $3$ 不稳定。

同理可证 $1,2,4,5$ 也不稳定。所以 $p=[2,4,3,5,1]$ 是合法答案。其他如 $[5,4,3,2,1]$ 或 $[3,5,1,4,2]$ 也是合法答案。

第三个测试用例：可以证明不存在这样的排列。