#P4796. [CERC2016]Key Knocking

    ID: 3913 传统题 1000ms 512MiB 尝试: 58 已通过: 26 难度: 5 上传者: 标签>难度分类普及+/提高-构造与建模分块构造局部修复模拟与实现技巧添加哨兵CF1800

[CERC2016]Key Knocking

[CERC2016] 敲击密钥 Key Knocking

题目描述

Goran 在做膝盖手术后的康复期间,研究了一种储存加密密钥的智能卡。密钥是一个长度为 3n3n 的二进制串,位的编号从左到右为 11 至 3n3n。密钥的权值等于相邻且不同的二进制位对数加 11。例如,000 的权值为 11,011010100 的权值为 77。

Goran 发现通过给智能卡电路施加短脉冲,可以同时翻转任意两个相邻的位。翻转把 0 改为 1,把 1 改为 0。例如,可以把 000 在一步内变成 110。

给定初始密钥,找出任意一种至多使用 nn 步的方案,使密钥的权值达到至少 2n2n。保证有解。

输入格式

一行一个长度为 3n3n 的二进制串,表示初始密钥。

输出格式

第一行一个整数 mm,表示操作次数,0≤m≤n0\le m\le n。

第二行按执行顺序给出 mm 个整数 a1,…,ama_1,\ldots,a_m。第 kk 步翻转第 aka_k 位和第 ak+1a_k+1 位,因此 1≤ak<3n1\le a_k<3n。

若初始密钥的权值已至少为 2n2n,可以只输出 0。

数据范围

1≤n≤1051\le n\le10^5。

样例 #1

样例输入 #1

000000000

样例输出 #1

3
2 5 6

样例 #2

样例输入 #2

111001000111

样例输出 #2

2
3 9

样例 #3

样例输入 #3

010101

样例输出 #3

0