A16633 · Wrong Binary Search

题目描述

给定一个整数 $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 // 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" 都被认为是肯定的输出。 如果有多组满足条件的答案，可以输出任意一种。

输入 #1

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

输出 #1

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