← 返回题目列表

Codeforces · 1510/J

J. 日本游戏

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

约瑟夫非常喜欢日本的文化。去年他学习了日本传统服装和视觉艺术,现在他正试图找出日本游戏“Nonogram”的秘密。

在游戏的一维版本中,有一排 $$$n$$$ 空单元格,其中一些需要用钢笔填充。有一个解决方案的描述称为 简介 — 一个正整数序列,表示连续的填充单元集的长度。例如,$$$[4, 3, 1]$$$ 的配置文件表示有四个、三个和一个填充单元格的集合(按该顺序),连续集合之间至少有一个空单元格。

$$$n = 12$$$ 和 $$$p = [4, 3, 1]$$$ 的合适解决方案。

错误的解决方案:前四个填充的单元格应该是连续的。

错误的解决方案:在最后一个填充的单元格之前至少应该有一个空单元格。

Joseph 发现对于某些数字 $$$n$$$ 和配置文件 $$$p$$$ 有很多方法可以填充单元格以满足配置文件。现在他正在求解由 $$$n$$$ 单元格和轮廓 $$$p$$$ 组成的非图。他已经创建了一个 面膜 $$$p$$$ 的 — 他已填写了非图的每个解决方案中必须填写的所有单元格。

$$$n = 12$$$ 和 $$$p = [4, 3, 1]$$$ 的掩码:上面所有填充的单元格都填充在每个解决方案中。

休息后,他丢失了源配置文件$$$p$$$。他只有$$$n$$$和面具$$$m$$$。帮助 Joseph 找到任何带有掩码 $$$m$$$ 的配置文件 $$$p'$$$,或者说不存在这样的配置文件并且 Joseph 犯了一个错误。

输入

唯一一行包含字符串 $$$m$$$ — 源配置文件 $$$p$$$ 的掩码。 $$$m$$$ 的长度为 $$$n$$$ ($$$1 \le n \le 100\,000$$$)。字符串 $$$m$$$ 由符号组成 # 和 _ — 分别表示已填充和空的单元格。

输出

如果不存在掩码 $$$m$$$ 的配置文件,则输出数字 $$$-1$$$。否则,在第一行输出一个整数 $$$k$$$ — 配置文件 $$$p'$$$ 中的整数个数。在第二行,输出配置文件$$$p'$$$的$$$k$$$整数。

示例

输入
复制

__#_____

输出
复制

2
3 2 

输入
复制

_#

输出
复制

-1

输入
复制

___

输出
复制

0