#2204. Constructing a matrix

    ID: 2204 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1655来源:qoj.ac数据:公开样例构造

Constructing a matrix

Constructing a matrix

题目描述

标题: Constructing a matrix - Problem - QOJ.ac

#16215. Constructing a matrix

Statistics

The problem was used in the following contests:

鲍勃有一个行数为 n,列数为 n 的矩阵。每个位置上都有一个介于 1 和 n2 之间的整数。鲍勃记得第 i(0≤i≤n−1)行里有 ai 个不同数字,第 i(0≤i≤n−1)列里有 bi 个不同数字。由于鲍勃不喜欢在整行或整列中重复相同的数字,所以 ai,bi≥2。

不知何故,鲍勃丢失了矩阵,现在只剩下a和b了。请帮助鲍勃恢复矩阵!任何满足给定 a 和 b 约束,且元素均介于 1 到 n2 的矩阵都被认为是正确的。

Implementation Details

你应该包含 matrix.h,并实现如下过程:

int[][] cons(int n, int[] a, int[] b)

  • n: 矩阵的边长。
  • a: 每行的不同数个数。
  • b: 每列的不同数个数。
  • 你实现的过程会被调用恰好一次。
  • 你应该返回一个 n×n 的你构造的矩阵 m。第 i 行第 j 列的元素应为 m[i][j]。
  • 输入保证存在解。

Example

考虑如下调用:cons(3, [2, 2, 3], [2, 3, 3])

一个合法的返回矩阵为 [[1, 2, 1], [2, 3, 2], [1, 9, 4]]。

Constraints

1≤n≤2000。

对于每个 1≤i≤n,2≤ai,bi≤n。

输入保证有解。

Subtasks

  1. (10分)n≤5
  2. (20分)n≤10
  3. (20分)n≤50
  4. (20分)对于每个 i,bi=2。
  5. (30分)无特殊限制。

Sample Grader

样例交互器以下列格式读取输入。

  • 第一行:n
  • 第二行:a[0] a[1] ⋯ a[n−1]
  • 第三行:b[0] b[1] ⋯ b[n−1]

样例交互器以下列格式打印你的输出。

  • 你构造的矩阵,每行之间用换行分割,每行内用空格分割

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2 2 3
2 3 3
1 2 1
2 3 2
1 9 4

样例 2

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