← 返回题目列表

Codeforces · 1740/G

G. 危险的激光功率

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

Pak Chanek 有一个 $$$n \times m$$$ 的门户网格。第 $$$i$$$ 行和 $$$j$$$ 列上的入口表示为入口 $$$(i,j)$$$。入口 $$$(1,1)$$$ 和 $$$(n,m)$$$ 分别位于网格的西北角和东南角。

门户$$$(i,j)$$$ 有两个设置:

- 键入 $$$t_{i,j}$$$,即 $$$0$$$ 或 $$$1$$$。
- 强度 $$$s_{i,j}$$$,是 $$$1$$$ 和 $$$10^9$$$(含)之间的整数。

当激光以 $$$x_\text{in}$$$ 速度进入入口 $$$(i, j)$$$ 的面 $$$k$$$ 时,它会离开入口 $$$(k+2+t_{i,j}) \bmod 4$$$,速度为 $$$x_\text{out} = \max(x_\text{in},s_{i,j})$$$。门户还必须消耗 $$$x_\text{out} - x_\text{in}$$$ 单位的能量。

Pak Chanek 今天很无聊。他将以 $$$1$$$ 的初始速度发射 $$$4nm$$$ 激光,每个入口的每个面各一束。每束激光都会穿过这个入口网格,直到移出网格或穿过 $$$10^{100}$$$ 入口。

最后,Pak Chanek 认为当且仅当该门户消耗的总能量模 $$$2$$$ 等于其类型时,该门户才是好的。给定所有门户的强度设置,找到一种方法来分配每个门户的类型设置,以使良好门户的数量最大化。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1000$$$) — 网格中的行数和列数。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含 $$$m$$$ 整数,第 $$$j$$$ 整数为 $$$s_{i,j}$$$ ($$$1 \leq s_{i,j} \leq 10^9$$$) — 门户 $$$(i, j)$$$ 的强度。

输出

打印 $$$n$$$ 行,每行包含长度为 $$$m$$$ 的字符串,该字符串由表示类型设置的字符 $$$0$$$ 或 $$$1$$$ 组成。第 $$$i$$$ 字符串中的第 $$$j$$$ 字符是门户 $$$(i, j)$$$ 的类型设置。

如果有多个解,则可以输出任意一个。

示例

输入 #1

2 3
8 8 2
6 5 7

输出 #1

110
100

输入 #2

1 2
420 69

输出 #2

10

注意

在第一个示例中,让我们考虑激光 Pak Chanek 射向传送门 $$$(2, 2)$$$ 的 $$$1$$$ 面。激光的传播过程如下:

1. 激光以 $$$1$$$ 速度进入入口 $$$(2, 2)$$$ 的面 $$$1$$$。它让门户变得面目全非$$$3$$$,速度为$$$5$$$。门户 $$$(2, 2)$$$ 消耗 $$$4$$$ 单位能量。
2. 激光以 $$$5$$$ 速度进入入口 $$$(2, 1)$$$ 的面 $$$1$$$。它让门户变得面目全非$$$0$$$,速度为$$$6$$$。门户 $$$(2, 1)$$$ 消耗 $$$1$$$ 单位能量。
3. 激光以 $$$6$$$ 速度进入入口 $$$(1, 1)$$$ 的面 $$$2$$$。它让门户变得面目全非$$$1$$$,速度为$$$8$$$。门户 $$$(1, 1)$$$ 消耗 $$$2$$$ 单位能量。
4. 激光以 $$$8$$$ 速度进入入口 $$$(1, 2)$$$ 的面 $$$3$$$。它让门户变得面目全非$$$2$$$,速度为$$$8$$$。门户 $$$(1, 2)$$$ 消耗 $$$0$$$ 单位能量。
5. 激光以 $$$8$$$ 速度进入入口 $$$(2, 2)$$$ 的面 $$$0$$$。它让门户变得面目全非$$$2$$$,速度为$$$8$$$。门户 $$$(2, 2)$$$ 消耗 $$$0$$$ 单位能量。

上面的激光行程示意图如下。

作为示例,请考虑门户 $$$(2, 3)$$$。我们可以计算出该门户最终消耗的总能量将为$$$32$$$。由于 $$$32 \bmod 2 = 0$$$ 且 $$$t_{2,3} = 0$$$,因此它是一个很好的门户。