[NordicOI 2022] 能源网格 Power Grid

ID: 10106

远端评测题

5000ms

1024MiB

尝试: 0

已通过: 0

难度: 7

上传者:

root

标签>

2022

Special Judge

NordicOI（北欧）

题目背景

译自 Nordic Olympiad in Informatics 2022 Power Grid。如果发现 SPJ 锅了请联系搬题人 qvq。

$\texttt{5s,1G}$ 。请不要滥用本题评测。

题目描述

有一座城市，由 $N$ 行 $M$ 列共 $N\times M$ 个方格组成。方格 $(i,j)$ 的电力消耗记为 $A_{i,j}$ 。这里， $A_{i,j}$ 可以为正数，负数或者 $0$ 。

对于方格 $(i,j)$ ，定义

C_{i, j} = \left| \sum _{k=1}^ N A_{k, j} - \sum _{k=1}^ M A_{i, k} \right|

即，一行的总用电量与一列的总用电量的差值的绝对值。

给定所有的 $C_{i,j}$ ，你能否构造出一组合法的 $A_{i,j}$ ？

数据保证至少存在一组解。

输入格式

第一行，两个正整数 $N,M$ ，含义见题面。

接下来 $N$ 行，第 $i$ 行第 $j$ 个数为 $C_{i,j}$ ，含义见题面。

保证至少存在一组解。

输出格式

输出 $N$ 行 $M$ 列，第 $i$ 行第 $j$ 个数为 $A_{i,j}$ 。

多解时，任意输出一组解均可。

你需要保证 $-2^{31}\le A_{i,j}\lt 2^{31}$ 。

输入数据 1

2 3
3 4 1
6 7 2

输出数据 1

1 2 6
5 3 4

输入数据 2

输出数据 2

0 0 0 0
0 0 0 0
0 0 0 0

提示

数据范围

$1\le N,M\le 1\, 000$ ；
$0\le C_{i,j}\le 1\, 000$ ；
保证至少存在一组解。

子任务

子任务编号	得分	限制
$1$	$8$	$N,M,C_{i,j}\le 3$
$2$	$5$	$N,M,C_{i,j}\le 6$
$3$	$11$	$N=1$
$4$	$6$	$N,M\ge 2$ ， $C_{i,j}$ 全相同
$5$	$15$	$N,M\ge 2$ ， $C_{i,j}$ 两两不同
$6$	$5$	$C_{i,j}\le 1$
$7$	$15$	$N=M$
$8$	$25$	$N,M,C_{i,j}\le 100$
$9$	$10$	无额外限制

#P10644. [NordicOI 2022] 能源网格 Power Grid