这是问题的困难版本。版本之间的区别在于,在该版本中,对数量的限制 1最终字符串中的剩余部分更加严格。只有解决了该问题的所有版本,您才能破解。
给你一个仅包含字符的二进制字符串 $$$s_1s_2\ldots s_n$$$ 0 和 1。您可以执行 $$$\lfloor\frac{n}{2}\rfloor$$$ 操作。在第 $$$x$$$ 操作中,您可以执行以下操作:
- 选择一个整数 $$$l$$$,使得 $$$0 \leq l \leq n-x$$$。如果$$$l=0$$$,则什么也不做。否则,字符 $$$s_l$$$ 和 $$$s_{l+x}$$$ 都会翻转。也就是说,对于每个字符,如果是$$$0$$$,那么就改为$$$1$$$,反之亦然。
你的任务是找到一系列操作,使得 二进制字符串中的 1最多剩余 $$$7$$$。可以证明,在这个问题的约束下,这总是可能的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2\cdot 10^6$$$)。
每个测试用例的第二行包含一个二进制字符串 $$$s_1s_2\ldots s_n$$$ ($$$s_i \in \{0,1\}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^6$$$。
输出
对于每个测试用例,在新行上输出 $$$\lfloor\frac{n}{2}\rfloor$$$ 数字:为操作 $$$1,2,\ldots,\lfloor\frac{n}{2}\rfloor (0 \leq l_x \leq n-x)$$$ 选择 $$$l$$$。你应该保证所有操作之后最多有$$$7$$$ 字符串中剩余 1 。
如果有多个解,则输出任意一个。
示例
输入复制
6300041101511101911111111110111111101115110011101010100
输出复制
0 1 1 1 3 6 2 0 2 1 0 0 0 0 13 6 8 5 2 8 1
注意
在第四个测试用例中:
- 最初,$$$s=$$$111111111。由于 $$$n=9$$$,我们执行 $$$\lfloor\frac{9}{2}\rfloor=4$$$ 操作。
- 第一个操作有$$$l=6$$$。因此,字符 $$$6$$$ 和 $$$6+1=7$$$ 被翻转。现在,$$$s=$$$111110011.
- 第二个操作有$$$l=2$$$。因此,字符 $$$2$$$ 和 $$$2+2=4$$$ 被翻转。现在,$$$s=$$$101010011.
- 第三个操作有$$$l=0$$$。因此,什么也不做。
- 第四个操作有$$$l=2$$$。因此,字符 $$$2$$$ 和 $$$2+4=6$$$ 被翻转。现在,$$$s=$$$111011011.
- 由于最终字符串有 $$$7$$$ 1和 $$$7 \leq 7$$$,这个解决方案是正确的。