CFCF2192B.Flipping Binary String

普及-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定一个长度为 nn 的二进制字符串 ss。你可以对字符串进行如下操作:

  • 选择一个下标 ii,并翻转除了第 ii 位以外所有位置上的比特。也就是说,选择一个整数 ii1in1 \le i \le n),对于所有 jj 满足 1jn1 \le j \le njij \ne i,如果 sj=0s_j = 0,则将 sjs_j 置为 11;否则将 sjs_j 置为 00

你可以对字符串进行任意次数的上述操作,但每个下标最多只能被选择一次。

你的任务是通过若干次操作,把字符串 ss 的所有比特都变为 00,或者判断这不可能做到。你不需要最小化操作次数。

输入格式

每个测试包含若干组测试数据。第一行包含测试组数 tt1t1041 \le t \le 10^4)。接下来是每组测试数据的描述。

每组测试数据的第一行包含一个整数 nn1n2×1051 \le n \le 2 \times 10^5)。

第二行是一个长度为 nn 的二进制字符串 ss

保证所有测试数据中 nn 的总和不超过 2×1052 \times 10^5

输出格式

对于每组测试数据,如果无法将所有比特变成 00,输出 1-1。否则,输出两行:

  • 第一行,输出操作次数 xx0xn0 \leq x \leq n)。
  • 第二行,输出 xx 个数,表示依次选择进行操作的下标。每个下标最多只能选择一次。

如果存在多组可行解,你可以输出任意一种。

输入输出样例

  • 输入#1

    4
    3
    101
    3
    100
    4
    0000
    4
    1010

    输出#1

    1
    2 
    -1
    0
    2
    1 3

说明/提示

在第一个样例中,对第 22 位进行操作,相当于翻转第 11 位和第 33 位的比特。操作后,字符串变为 000000

在第二个样例中,可以证明无法通过上述操作将字符串 aa 变为 000000

首页