← 返回题目列表

Codeforces · 2146/C

C. 错误的二分查找

中文机器翻译题面 查看原题

给定一个整数 $$$n$$$ 和一个长度为 $$$n$$$ 的二进制字符串$$$^{\text{*}}$$$ $$$s$$$。

对于长度为 $$$n$$$ 的排列 $$$^{\text{†}}$$$ $$$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$$$) 稳定 当且仅当 $$$\text{find}(x)$$$ 是 总是 不是未定义且 $$$p_{\text{find}(x)}=x$$$ 无论在伪代码过程中如何选择 $$$m$$$ 的值, 总是 都成立。

您必须构造一个长度为 $$$n$$$ 的排列 $$$p$$$,这样:

  • 对于每个 $$$1\le i\le n$$$,整数 $$$i$$$ 为 稳定 当且仅当 $$$s_i=\mathtt{1}$$$。

或者确定不存在这样的排列。

$$$^{\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}$$$ 或 $$$\mathtt{1}$$$)。

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

输出

对于每个测试用例:

  • 如果不存在这样的排列,则打印“NO”在唯一的输出行中。
  • 否则,打印“是”在输出的第一行。然后在第二行输出 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$) — 您构建的排列。

您可以在任何情况下输出令牌(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

如果有多个答案,您可以打印其中任何一个。

示例

输入
复制

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$$$ 作为 $$$l=1$$$ 和 $$$r=3$$$ 之间的随机整数。
    • 如果我们选择 $$$m=1$$$:
      • $$$p_1=1 \lt 2$$$,因此 $$$l$$$ 设置为 $$$m + 1 = 2$$$。现在$$$l=2$$$ 和$$$r=3$$$;
      • 我们将选择 $$$m$$$ 作为 $$$l=2$$$ 和 $$$r=3$$$ 之间的随机整数。
      • 如果我们选择$$$m=2$$$:$$$p_2=2$$$,那么返回值为$$$2$$$。
      • 如果我们选择$$$m=3$$$:$$$p_3=3 \gt 2$$$,那么$$$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$$$;
  • 我们将选择 $$$m$$$ 作为 $$$l=1$$$ 和 $$$r=5$$$ 之间的随机整数。我们选择$$$m=2$$$;
  • $$$p_2=4 \gt 3$$$,因此 $$$r$$$ 设置为 $$$m-1=1$$$。现在$$$l=1$$$ 和$$$r=1$$$;
  • 我们将选择 $$$m$$$ 作为 $$$l=1$$$ 和 $$$r=1$$$ 之间的随机整数。我们只能选择$$$m=1$$$;
  • $$$p_1=2 \lt 3$$$,因此 $$$l$$$ 设置为 $$$m + 1 = 2$$$。现在$$$l=2$$$ 和$$$r=1$$$;
  • 由于 $$$l \gt r$$$,退出循环并且返回值未定义。

因此,$$$\text{find}(3)$$$的返回值是未定义的,因此整数$$$3$$$不是 稳定.

类似地,我们可以证明整数 $$$1$$$、$$$2$$$、$$$4$$$ 和 $$$5$$$ 也不是 稳定。因此,$$$p = [2, 4, 3, 5, 1]$$$ 是一个有效的答案。

其他一些排列,例如 $$$p=[5,4,3,2,1]$$$ 和 $$$p=[3,5,1,4,2]$$$,也是有效的答案。您可以打印其中任何一个。

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