← 返回题目列表

Codeforces · 2183/I2

I2. 配对翻转(困难版)

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

这是问题的困难版本。版本之间的区别在于,在该版本中,对数量的限制 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 。

如果有多个解,则输出任意一个。

示例

输入
复制

6
3
000
4
1101
5
11101
9
111111111
10
1111111011
15
110011101010100

输出
复制

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$$$,这个解决方案是正确的。