← 返回题目列表

AtCoder · abc432_d

D. 突然,一场暴风雨

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

分数: 425 点

问题陈述

有一个无限大的二维网格。细胞颜色 (x,y) 为黑色,如果 0 \leq x \leq X-1 和 0 \leq y \leq Y-1,否则为白色。

N 巨大的风暴在这个网格上按顺序发生。的 i-th 大风暴根据字符表示的规则更新网格上每个单元格的颜色 C_i 和整数 A_i, B_i.

在 i-th大风暴,细胞的颜色 (x, y) 大风暴过后是:

  • 万一 C_i is X,
    • if x < A_i,它变成单元格的颜色 (x, y + B_i) 大风暴之前;
    • if x \geq A_i,它变成单元格的颜色 (x, y - B_i) 大风暴之前。
  • 万一 C_i is Y,
    • if y < A_i,它变成单元格的颜色 (x + B_i, y) 大风暴之前;
    • if y \geq A_i,它变成单元格的颜色 (x - B_i, y) 大风暴之前。

两个黑色单元格 (x_1, y_1), (x_2, y_2) 是 相邻 当且仅当 |x_1 - x_2| + |y_1 - y_2| = 1。另外,还有两个黑细胞 c_1, c_2 是 已连接 当且仅当一个人可以从单元格中移动 c_1 到单元格 c_2 通过重复移动到相邻的黑色单元格。

非空集 黑色单元格的 S 是 连接的组件 当且仅当 S 满足以下条件:

  • 中的任意两个单元格 S 已连接。
  • 每个黑色单元格都不在 S 未连接到任何单元格 S.

毕竟是为了格子 N 大风暴发生了,求连通分量的数量并输出每个连通分量中的单元格数量 按升序排列.

约束

  • N, X, Y 是整数。
  • 1 \leq N \leq 14
  • 1 \leq X,Y \leq 10^8
  • C_i is X or Y.
  • A_i, B_i 是整数。
  • -10^8 \leq A_i, B_i \leq 10^8

输入

输入由标准输入按以下格式给出:

N X Y
C_1 A_1 B_1
\vdots
C_N A_N B_N

输出

输出两行。

第一行应包含由黑色单元格组成的连接组件的数量。

第二行应包含每个连接组件中的单元格数量,以空格分隔, 按升序排列.


示例输入 1

2 3 5
X 2 2
Y -1 1

示例输出 1

2
2 13

由于大风暴,网格发生如下图所示的变化(向右方向为正方向) x- 轴,向上方向为正方向 y-轴)。

在最终网格中,存在以下两个连通分量:

  • 由单元组成的连接组件 (-1,-2), (0,-2).
  • 由单元组成的连接组件 (1,-1), (1,0), (1,1), (1,2), (2,-1), (2,0), (2,1), (2,2), (3,2), (3,3), (3,4), (3,5), (3,6).

注意必须输出每个连通分量中的单元格数量 按升序排列.


示例输入 2

14 68875272 94216928
X 1630731 32914676
X 17164413 -33684569
X 26798060 5418308
X 34094469 -45675954
X 43889566 34125482
X 56836569 -22217058
X 64045210 27857939
Y -54561094 11587606
Y 93548188 32214521
Y -77361096 25750481
Y 27724899 1810420
Y 80945185 -7871305
Y 14782822 -2565089
Y 54687684 -22884393

示例输出 2

8
21105046168287 22050167303226 33624667752182 223328231190194 441936776830492 1141371400772596 1141702254882183 3464097998105256

输出值可能不适合 32 位整数。