CF2271G.Grid Filling

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a grid of size n×mn \times m. The rows are numbered from 11 to nn from top to bottom, and the columns are numbered from 11 to mm from left to right. Two cells are adjacent if they share a side.

There are hh horizontal and vv vertical cuts in the grid. The ii-th horizontal cut goes between rows rir_i and ri+1r_i + 1, and the jj-th vertical cut goes between columns cjc_j and cj+1c_j + 1; every cut crosses the whole grid. Together with the borders of the grid, the cuts split it into (h+1)⋅(v+1)(h + 1) \cdot (v + 1) rectangular pieces.

Write a positive integer in every cell of the grid so that both of the following conditions hold:

  • any two adjacent cells contain different integers, even if these cells belong to different pieces;
  • every piece consisting of xx cells contains each of the integers 1,2,…,x1, 2, \ldots, x exactly once.

Find any way to fill the grid satisfying these conditions, or determine that it is impossible.

你被给定一个大小为 n×mn \times m 的网格。行从上到下编号为 11 到 nn,列从左到右编号为 11 到 mm。若两个格子共享一条边,则称它们相邻。

网格中有 hh 条水平切割线和 vv 条垂直切割线。第 ii 条水平切割线位于第 rir_i 行与第 ri+1r_i + 1 行之间,第 jj 条垂直切割线位于第 cjc_j 列与第 cj+1c_j + 1 列之间;每条切割线均横贯整个网格。这些切割线连同网格的边界一起,将网格划分为 (h+1)⋅(v+1)(h + 1) \cdot (v + 1) 个矩形区域。

请在网格的每个格子中填入一个正整数,使得以下两个条件同时成立:

  • 任意两个相邻格子中的整数互不相同(即使这两个格子属于不同的区域);
  • 每个由 xx 个格子组成的区域,必须恰好包含整数 1,2,…,x1, 2, \ldots, x 各一次。

请找出一种满足上述条件的填数方案,或判定该问题无解。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤10001 \le t \le 1000). The description of the test cases follows.

The first line of each test case contains four integers nn, mm, hh, and vv (1≤n,m≤10001 \le n, m \le 1000, 0≤h<n0 \le h \lt n, 0≤v<m0 \le v \lt m) — the number of rows of the grid, the number of columns of the grid, the number of horizontal cuts, and the number of vertical cuts.

The next line contains hh integers r1,r2,…,rhr_1, r_2, \ldots, r_h (1≤r1<r2<…<rh<n1 \le r_1 \lt r_2 \lt \ldots \lt r_h \lt n) — the positions of the horizontal cuts. If h=0h = 0, this line is not present.

The next line contains vv integers c1,c2,…,cvc_1, c_2, \ldots, c_v (1≤c1<c2<…<cv<m1 \le c_1 \lt c_2 \lt \ldots \lt c_v \lt m) — the positions of the vertical cuts. If v=0v = 0, this line is not present.

It is guaranteed that the sum of nn over all test cases does not exceed 10001000.

It is guaranteed that the sum of mm over all test cases does not exceed 10001000.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤10001 \le t \le 1000)。随后是各测试用例的描述。

每个测试用例的第一行包含四个整数 nn、mm、hh 和 vv(1≤n,m≤10001 \le n, m \le 1000,0≤h<n0 \le h \lt n,0≤v<m0 \le v \lt m)—— 分别表示网格的行数、列数、水平切割次数和垂直切割次数。

接下来的一行包含 hh 个整数 r1,r2,…,rhr_1, r_2, \ldots, r_h(1≤r1<r2<…<rh<n1 \le r_1 \lt r_2 \lt \ldots \lt r_h \lt n)—— 表示水平切割的位置。若 h=0h = 0,则该行不存在。

再下一行包含 vv 个整数 c1,c2,…,cvc_1, c_2, \ldots, c_v(1≤c1<c2<…<cv<m1 \le c_1 \lt c_2 \lt \ldots \lt c_v \lt m)—— 表示垂直切割的位置。若 v=0v = 0,则该行不存在。

保证所有测试用例中 nn 的总和不超过 10001000。

保证所有测试用例中 mm 的总和不超过 10001000。

输出格式

For each test case, if there is no valid way to fill the grid, output −1-1.

Otherwise, output nn lines. The ii-th of these lines should contain mm integers — the numbers written in the cells of the ii-th row of the grid, from left to right.

If there are multiple valid ways to fill the grid, output any of them.

对于每个测试用例,若不存在填充网格的有效方案,则输出 −1-1。

否则,输出 nn 行。其中第 ii 行应包含 mm 个整数——即网格第 ii 行中从左到右各单元格所填的数字。

若存在多种有效的填充方案,输出任意一种即可。

输入输出样例

  • 输入#1

    4
    3 3 0 0
    1 6 0 2
    1 3
    5 5 2 2
    2 3
    2 3
    4 4 2 2
    1 2
    1 2

    输出#1

    1 2 3
    4 5 6
    7 8 9
    1 2 1 2 1 3
    1 2 1 2 1
    3 4 2 3 4
    1 2 1 2 1
    3 4 2 3 4
    1 2 1 2 1
    -1

说明/提示

In the first example, one possible way to fill the grid is shown below:

In the third example, the dashed lines represent the cuts. One possible way to fill the grid is shown below:

In the fourth example, it can be shown that no valid filling exists.

在第一个例子中,一种可能的网格填充方式如下所示:

在第三个例子中,虚线表示切割线。一种可能的网格填充方式如下所示:

在第四个例子中,可以证明不存在合法的填充方案。

输入解题思路,AI测评打分。不知道怎么写?

首页