← 返回题目列表

Codeforces · 1137/A

A. 摩天大楼

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

朵拉非常喜欢冒险。在一次旅行中,她遇到了一座神奇的城市,它由东边的$$$n$$$街道和南边的$$$m$$$街道组成。当然,这个城市有 $$$nm$$$ 十字路口。在第$$$i$$$东街和第$$$j$$$南街的任何交叉路口都有一座巨大的摩天大楼。朵拉立刻产生了好奇心,决定去探索城市建筑的高处。

当朵拉穿过第 $$$i$$$ 东街和第 $$$j$$$ 南街的交叉路口时,她检查了这两条街道。当朵拉得知这两条街上所有摩天大楼的高度后,她想知道:如何重新分配这两条街上摩天大楼的高度,使得最大高度尽可能小,并且比较一条街上任意两座摩天大楼的高度的结果不会改变。

形式上,在每个 $$$nm$$$ 交叉点上,Dora 都解决了一个独立的问题。她看到 $$$n + m - 1$$$ 摩天大楼,并且对于每座摩天大楼,她都知道其真实高度。此外,可以比较任意两个高度以获得“更大”、“更小”或“等于”的结果。现在,Dora 想要选择一些整数 $$$x$$$ 并为每个摩天大楼分配一个从 $$$1$$$ 到 $$$x$$$ 的高度。在指定高度时,Dora 希望保留两条街道上摩天大楼的相对顺序。也就是说,当前东街两座摩天大楼的高度比较结果不应改变,当前南街两座摩天大楼高度比较的结果也不应改变。请注意,位于南街的摩天大楼不与仅位于东街的摩天大楼进行比较。然而,位于街道交叉口的摩天大楼可以与南部和东部的摩天大楼进行比较。对于每个交叉点,Dora 想要独立计算可能的最小 $$$x$$$。

例如,如果交叉路口及其对应的两条街道如下所示:

那么最好按如下方式替换摩天大楼的高度(请注意,保留东部街道内和南部街道内的所有比较“小于”、“等于”、“更大”)

最大的使用数字是 $$$5$$$,因此这个交集的答案将是 $$$5$$$。

帮助朵拉计算每个交叉路口的答案。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1000$$$) – 向东的街道数量和向南的街道数量。

以下 $$$n$$$ 行中的每一行都包含 $$$m$$$ 整数 $$$a_{i,1}$$$、$$$a_{i,2}$$$、...、$$$a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^9$$$)。位于第 $$$i$$$ 行中第 $$$j$$$ 个位置的整数 $$$a_{i,j}$$$ 表示第 $$$i$$$ 东边街道和第 $$$j$$$ 南向交叉处的摩天大楼的高度。

输出

打印 $$$n$$$ 行,每行包含 $$$m$$$ 个整数。位于第 $$$i$$$ 行内第 $$$j$$$ 个位置的整数 $$$x_{i,j}$$$ 是第 $$$i$$$-th Eastern 街道和 $$$j$$$-th Southern 街道交叉口问题的答案。

示例

输入 #1

2 3
1 2 1
2 1 2

输出 #1

2 2 2 
2 2 2

输入 #2

2 2
1 2
3 4

输出 #2

2 3 
3 2

注意

在第一个示例中,不可能减少任何交叉点处问题的最大使用高度,因此我们不必更改任何高度。

在第二个示例中,答案如下:

- 对于第一行和第一列的交集
- 对于第一行和第二列的交集
- 对于第二行和第一列的交点
- 对于第二行和第二列的交点