CF2136B Like the Bitset

给定一个长度为 $n$ 的二进制字符串 $s$，以及一个整数 $k$。 Aquawave 想要构造一个长度为 $n$ 的排列 $p$，使得对于所有 $1 \le i \le n$ 且 $s_i = \mathtt{1}$ 的下标 $i$，满足如下条件： - 对于每一个长度不少于 $k$ 的区间 $[l, r]$（即 $r - l + 1 \geq k$）且覆盖位置 $i$（即 $l \leq i \leq r$），该区间内的最大元素 $p_l, p_{l+1}, \ldots, p_r$ 中，最大值不能等于 $p_i$。 注意，对于 $s_i = \mathtt{0}$ 的下标 $i$ 没有上述限制。 请你找出这样一个排列，或者判断不存在这样的排列。 $^{\text{∗}}$ 二进制字符串指的是每个字符都是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。 $^{\text{†}}$ 长度为 $n$ 的排列是一个由 $n$ 个互不相同的 $1$ 到 $n$ 的整数构成的数组，例如 $[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（长度为 $3$，但出现了 $4$）。

每组测试数据包含多组测试用例。第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每个测试用例的第一行输入两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq n$），分别表示字符串 $s$ 的长度和给定的整数。 第二行输入一个长度为 $n$ 的二进制字符串 $s$（$s_i = \mathtt{0}$ 或 $\mathtt{1}$）。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每组测试用例： - 如果存在至少一个满足条件的排列，请： - 在第一行输出 YES（大小写均可）； - 在第二行输出 $n$ 个两两不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），即你构造的排列。 - 否则输出 NO。 如果存在多组解，输出任意一组均可。

在第一个测试用例中，你可以输出任意长度为 $n = 2$ 的排列，因为所有 $s_i$ 都等于 $\mathtt{0}$。 在第二个测试用例中，$p=[1, 4, 3, 2]$ 是一个合法解，因为： - 唯一一个 $s_i = \mathtt{1}$ 的位置是 $i = 3$，覆盖 $3$ 且长度不少于 $k=3$ 的区间共有三个，分别为 $[1, 3]$，$[1, 4]$ 和 $[2, 4]$； - 对于这三个区间，每个区间的最大值都是 $p_2 = 4$，显然最大值不等于 $p_3 = 3$。 由 ChatGPT 5 翻译