#P17918. Easy Tetris

Easy Tetris

Easy Tetris

在一个宽度为 1010、高度无限的棋盘上玩俄罗斯方块,棋盘初始为空。接下来按照给定顺序落下 NN 个方块,只有以下两种形状:

  • I:高 44、宽 11 的竖直长条。
  • O:高 22、宽 22 的实心正方形。

棋盘的列从左到右编号为 11 到 1010。每个方块落下前,你选择它的横向位置:I 可以放在任意一列;O 的左侧列可以是 11 到 99 中的任意一列。

方块随后竖直下落,直到碰到棋盘底部或已有方块。不能旋转方块,不能在下落过程中横向移动,也不能拆分方块。落定后,方块覆盖的格子全部被填满。注意,O 落在高度不同的两列上方时,可能在下方留下空洞。

某一行的 1010 个格子全部被填满时,这一行会被消除,其上方的所有格子向下移动一格。同一次落块形成的所有满行会同时消除。

如果一次落块恰好同时消除 44 行,称为获得一次 tetris,得分加 11。消除其他数量的行不增加得分。

求最大可能得分,并输出一种达到最大得分的落块方案。

输入格式

第一行一个整数 NN,表示方块数量。

第二行一个长度为 NN、只包含 I 和 O 的字符串,依次描述方块类型。

输出格式

第一行输出一个整数,表示最大得分。

第二行输出 NN 个整数 c1,c2,…,cNc_1,c_2,\ldots,c_N:

  • 若第 ii 个方块为 I,cic_i 为它所在的列,要求 1≤ci≤101\le c_i\le10。
  • 若第 ii 个方块为 O,cic_i 为它的左侧列,要求 1≤ci≤91\le c_i\le9。

输出的方案必须实际获得第一行声明的最大得分。有多种最优方案时,可以输出任意一种。

数据范围

1≤N≤2000001\le N\le200000。每个输入文件只有一组数据。

样例

10
IIOIOIOOII
1
1 2 3 5 3 6 7 7 9 10

样例输出只是一种最优方案。