题目描述

这是一道交互题（吗？）。

Kevin 正在完成 $T$ 幅艺术品。

事实上，这其实就是一个 $N$ 行 $M$ 列的表格（或许我们可以将它看成一个围棋棋盘？），Kevin 的手上有非常非常多的黑色小卡片与白色小卡片，他可以随意的将黑色小卡片和白色小卡片放到表格内。

但是他完成这个艺术品后需要将它交给 scy 检查。scy 是一个对艺术品有着很高要求的艺术家，他觉得一幅合格的艺术品需要满足这些条件，不然 Kevin 就要遭到痛斥了：

• 对于这个艺术品的每一行，黑色卡片与白色卡片中数量较少的那种的数量应该为 $A$。

• 对于这个艺术品的每一列，黑色卡片与白色卡片中数量较少的那种的数量应该为 $B$。

Kevin 可不想被骂，但他是一个艺术造诣为 $0$ 的手残党，所以他把这个艰巨的任务交给了你，那么就由你来设计这个艺术品吧！

实现细节

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 table.h，即在程序开头加入以下代码：

#include "table.h"

选手需要在提交的程序源文件 table.cpp 中实现以下两个函数：

void init(int c, int T);

• $c, t$ 分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。
• 对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

std::vector<std::vector<int>> solve(int N, int M, int A, int B);

• $N, M$ 表示矩阵的行数和列数，$A, B$ 为题面所述的条件参数。
• 该函数需要返回一个 $n \times m$ 的二维数组（元素仅为 0 或 1），表示满足条件的填写方案。
• 如果无法满足条件，请返回一个空的 std::vector<vector<int>>。
• 对于每个测试点，该函数会被交互库调用恰好 $t$ 次。

注意：在任何情况下，最终测试时所用的交互库运行所需时间均不会超过 $0.1$ 秒，所用内存为固定大小，且均不超过 $64$ MiB。

测试程序方式

试题目录下的 grader.cpp 是交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp table.cpp -o table -std=gnu++14 -O2 -static

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号和测试数据组数。
  • 接下来依次为每组测试数据，对于每组测试数据，包含一行四个非负整数 $n, m, A, B$。
• 可执行文件将输出以下格式的数据至标准输出：
  • 对于每组测试数据，输出一行字符串表示测试结果：
    • Correct 表示选手返回的结果正确；
    • Wrong answer 表示选手返回的结果错误或格式不合法。

样例 1

输入

0 2
3 3 1 1
1 5 2 0

输出

Correct
Correct

样例 1 解释

该样例共包含两组测试数据。

对于第一组测试数据，$n=3, m=3, A=1, B=1$。 一种可能的交互过程为：

• 调用 solve(3, 3, 1, 1)，返回矩阵：

  1 0 0
  0 1 0
  0 0 1
  

  交互库验证每行和每列的 0 与 1 的较小值均为 $1$，判定为正确。

对于第二组测试数据，$n=1, m=5, A=2, B=0$。 一种可能的交互过程为：

• 调用 solve(1, 5, 2, 0)，返回矩阵：

  0 1 0 1 0
  

  交互库验证通过，判定为正确。

样例 2

见选手目录下的 table/table2.in 与 table/table2.ans。

该样例满足测试点 $1 \sim 4$ 的约束条件。

样例 3

见选手目录下的 table/table3.in 与 table/table3.ans。

该样例满足测试点 $5 \sim 8$ 的约束条件。

样例 4

见选手目录下的 table/table4.in 与 table/table4.ans。

该样例满足测试点 $11 \sim 12$ 的约束条件。

样例 5

见选手目录下的 table/table5.in 与 table/table5.ans。

该样例满足测试点 $15 \sim 20$ 的约束条件。

下发文件说明

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. table.h 是头文件，选手不用关心具体内容。
3. template_table.cpp 是提供的示例代码，选手可参考并实现自己的代码。

选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的 table.cpp，对该程序以外文件的修改不会影响评测结果。

数据范围

对于所有测试数据，均有：

• $1 \le T \le 10^4$；
• $1 \le N, M \le 1000$；
• $0 \le A$，$2 \times A \le m$；
• $0 \le B$，$2 \times B \le n$；
• 保证所有测试数据的 $\sum (N \times M) \le 10^6$；
• 输入的所有数值均为整数。

测试点编号	$T \le$	$N, M \le$	特殊性质
$1 \sim 4$	$10$	$10$	无
$5 \sim 8$	$10^4$
$9 \sim 10$	$100$
$11 \sim 12$			A
$13 \sim 14$	$1$	$1000$
$15 \sim 20$			无

• 特殊性质 A：$A = 0$。

评分方式

注意：

• 选手不应当通过非法方式获取交互库的内部信息，如直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同。

本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。选手只能在程序中访问自己定义的变量以及交互库给出的变量，尝试访问其他地址空间将可能导致编译错误或运行错误。

每次调用 solve 函数时，若返回的矩阵不被认为是正确的，或返回的矩阵中包含非 0/1 的非法元素，或返回的矩阵维度不匹配，则相应测试点得 $0$ 分。

在上述条件基础上，若选手通过了该测试点的所有 $T$ 组数据验证，则获得该测试点的满分；否则得 $0$ 分。