bzoj#P4796. [CERC2016] Key Knocking

[CERC2016] Key Knocking

题目描述

Goran 正在从他的膝盖手术中恢复,并正在试验用于存储的智能卡加密密钥。在这个问题中,一个密钥是指一个长度为 3n3n 的二进制序列,其中 nn 是正整数。序列的每一位从左往右依次被编号为 113n3n。一个密钥的权值是指相邻位不同的位置个数再加上 11。比如:000\text{000} 的权值是 11011010100\text{011010100} 的权值是 77

他发现他可以发送小型脉冲电流来修改智能卡的电路,从而修改密钥。确切地说,他可以不断进行下面的操作:选择任意两个相邻的位,然后同时取反它们。比如他可以通过一次操作把 000\text{000} 修改为 110\text{110}

给定一个长度为 3n3n 的密钥,请操作不超过 nn 次,将其修改为一个权值不少于 2n2n 的密钥。你可以认为合法解必然存在。

输入格式

包含一行一个 0101 序列,表示初始密钥,保证长度一定为 3n3n

输出格式

第一行包含一个整数 mm,表示操作的次数,你需要保证 0mn0\le m\le n

第二行包含 mm 个正整数 a1,a2,,am(1ai<3n)a_1,a_2,\cdots,a_m(1\le a_i<3n),依次表示每次翻转第 aia_i 和第 ai+1a_{i+1} 位。

如果初始密钥的权值已经不小于 2n2n,你可以仅输出一行一个整数 00

111001000111
2
3 9

数据规模与约定

对于 100%100\% 的数据,1n1051\le n \le 10^5