[NordicOI 2022] 能源网格 Power Grid

Luogu

IDLGP10644

Time5000ms

Memory1024MB

DifficultyP7

2022Special JudgeNordicOI（北欧）

有一座城市，由 $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}$？数据保证至少存在一组解。 ## Input 第一行，两个正整数 $N,M$，含义见题面。接下来 $N$ 行，第 $i$ 行第 $j$ 个数为 $C_{i,j}$，含义见题面。保证至少存在一组解。 ## Output 输出 $N$ 行 $M$ 列，第 $i$ 行第 $j$ 个数为 $A_{i,j}$。多解时，任意输出一组解均可。你需要保证 $-2^{31}\le A_{i,j}\lt 2^{31}$。 [samples] ## Background 译自 Nordic Olympiad in Informatics 2022 [Power Grid](https://noi22.kattis.com/contests/noi22/problems/powergrid)。如果发现 SPJ 锅了请联系搬题人 qvq。 $\texttt{5s,1G}$。**请不要滥用本题评测。** ## Note #### 数据范围 - $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$ | 无额外限制 |

Samples

Input #1

2 3
3 4 1
6 7 2

Output #1

1 2 6
5 3 4

Input #2

Output #2

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

API Response (JSON)

{
  "problem": {
    "name": "[NordicOI 2022] 能源网格 Power Grid",
    "description": {
      "content": "有一座城市，由 $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| $$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10644"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一座城市，由 $N$ 行 $M$ 列共 $N\\times M$ 个方格组成。方格 $(i,j)$ 的电力消耗记为 $A_{i,j}$。这里，$A_{i,j}$ 可以为正数，负数或者 $0$。\n\n对于方格 $(i,j)$，定义\n\n$$C_{i, j} = \\left|\n    \\sum _{k=1}^ N A_{k, j} - \\sum _{k=1}^ M A_{i, k} \\right| $$\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments