星图（starmap）

• 题目类型：函数提交题 / grader 评测
• 推荐时间限制：10 s
• 推荐空间限制：512 MiB
• 源文件：提交一个 C++ 源文件，实现指定函数即可

题目背景

星图铺就的，未必是归途。
但有人循着它，便不算迷路。

题目描述

夜空中共有 $n$ 个星座，每个星座有 $m$ 个星辰，每个星辰有一个初始璀璨程度 $a_{i,j}$，其中 $0 \le i < n, 0 \le j < m$。每个星辰的璀璨程度是 $1 \sim n$ 中的正整数。

古籍中记载了一种神秘的仪式，可以改变夜空中的星座状态。具体地，每次举行仪式时，需要选择恰好 $n$ 个属于不同星座的星辰，然后将这些星辰旋转：对于所有 $0 \le i < n$，星座 $i$ 中被选择的星辰会移动到星座 $(i+1) \bmod n$。

由于仪式的耗材有限，这种仪式只能举行至多 $p$ 次，其中 $p \ge nm$。$p$ 的具体取值见「数据范围」。

初始状态的夜空是不和谐的。当每个星座中所有星辰的璀璨程度全部相同时，夜空会变得和谐。你需要判断在举行至多 $p$ 次仪式后，夜空能否变得和谐，并尽可能给出一种相应的举行仪式方案。

Hydro 提交说明

本题为 函数提交题。

选手只需要提交一个 C++ 源文件，实现 starmap.h 中声明的函数。系统会自动将选手代码与官方提供的 grader.cpp、starmap.h 一起编译。

提交代码中应包含：

#include "starmap.h"

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

选手 不应该 自行从标准输入读入数据，也 不应该 自行向标准输出输出答案。所有数据会由评测器传入函数，选手应通过调用评测器提供的函数完成报告和构造。

需要实现的函数

选手需要在提交的源文件中实现以下两个函数。

void init(int c, int t);

• c 表示测试点编号。c = 0 表示该测试点为样例。
• t 表示当前测试点包含的测试数据组数。
• 对于每个测试点，该函数会在程序开始运行时被评测器调用恰好一次。

void starmap(int n, int m, std::vector<std::vector<int>> a);

• n 表示星座数量。
• m 表示每个星座的星辰数量。
• 对于 $0 \le i < n, 0 \le j < m$，$a_{i,j}$ 表示初始时第 $i$ 个星座第 $j$ 个星辰的璀璨程度。
• 对于每个测试点，该函数会被评测器调用恰好 $t$ 次。

可以调用的函数

选手可以通过调用以下函数报告当前测试数据是否可行：

void report(bool x);

• x = false 表示你认为无法在限制内使夜空变得和谐。
• x = true 表示你认为可以在限制内使夜空变得和谐。
• 每次 starmap 被调用时，选手必须恰好调用一次 report。

选手可以通过调用以下函数举行一次仪式：

void rotate(std::vector<int> b);

• b_0, b_1, \ldots, b_{n-1} 表示选择的 $n$ 颗星辰的璀璨程度。
• 选手需要保证 b 的长度为 $n$。
• 对于所有 $0 \le i < n$，在调用 rotate 时，第 $i$ 个星座中必须存在至少一个璀璨程度为 $b_i$ 的星辰。
• 璀璨程度相同的星辰无需区分。
• 调用后，第 $i$ 个星座中选择的星辰会移动到第 $(i+1) \bmod n$ 个星座。

调用限制：

• 只有在已经调用 report(true) 之后，才可以调用 rotate。
• 如果调用了 report(false)，则不能再调用 rotate。
• 每次 starmap 调用中，rotate 的调用次数不能超过 $p$。

若 report 或 rotate 的调用方式不合法，或 rotate 调用次数超过限制，则该测试点不得分。

本地测试方式

题目目录下的 grader.cpp 是评测器参考实现。最终评测时使用的评测器与参考实现的行为保持一致，但选手程序不应依赖评测器内部实现。

选手可以在本地使用如下命令编译：

g++ grader.cpp starmap.cpp -o starmap -std=c++14 -O2 -static

其中 starmap.cpp 为选手提交文件。

本地运行时，可执行文件从标准输入读入数据，格式如下：

第一行包含两个非负整数 $c,t$，分别表示测试点编号和测试数据组数。

接下来依次给出每组测试数据。对于每组测试数据：

第一行包含两个正整数 $n,m$，分别表示星座数量与每个星座的星辰数量。

接下来 $n$ 行，第 $i+1$ 行包含 $m$ 个正整数 $a_{i,j}$，表示初始时第 $i$ 个星座第 $j$ 个星辰的璀璨程度。

本地参考评测器会对每组测试数据输出一行一个整数：

• -1：操作不合法或超出限制；
• 0：选手报告无解；
• -2：选手报告有解，但所有仪式结束后没有满足条件；
• 正整数：选手报告有解，且所有仪式结束后满足条件，该整数表示操作次数。

注意：在 Hydro 上提交时，选手程序不需要直接输出这些内容；这些内容由后台评测器产生，并由 special judge 判断。

样例 1 输入

0 1
2 4
1 2 1 2
2 1 2 1

样例 1 输出

1

样例 2 输入

0 2
2 2
1 1
1 2
3 3
1 2 3
2 3 1
3 1 2

样例 2 输出

0
1

样例说明

样例输出中的 0/1 表示对应测试数据是否存在可行方案：

• 0 表示无解；
• 1 表示有解。

在 Hydro 的函数提交评测中，选手程序不应直接输出样例输出中的 0/1，而应通过 report 与 rotate 完成报告和构造。

其他样例

• 样例 3 见题目附件中的 starmap3.in 与 starmap3.ans，该样例满足子任务 1 的约束条件。
• 样例 4 见题目附件中的 starmap4.in 与 starmap4.ans，该样例满足子任务 2 的约束条件。
• 样例 5 见题目附件中的 starmap5.in 与 starmap5.ans，该样例满足子任务 3 的约束条件。
• 样例 6 见题目附件中的 starmap6.in 与 starmap6.ans，该样例满足子任务 4 的约束条件。
• 样例 7 见题目附件中的 starmap7.in 与 starmap7.ans，该样例满足子任务 5 的约束条件。

数据范围

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

• $1 \le t \le 1000$；
• $2 \le n,m \le 500$；
• $nm \le p = \min\left\{n^2m, \left\lfloor \dfrac{4 \times 10^8}{tn} \right\rfloor\right\}$；
• $np \le 4 \times 10^8$；
• 对于所有 $0 \le i < n, 0 \le j < m$，均有 $1 \le a_{i,j} \le n$。

子任务编号	$t=$	$n,m \le$	特殊性质	分值
1	1000	10	是	20
2			否
3	100		是
4			否
5	3	500

特殊性质：保证 $m = 2$。

评分方式

注意：

• 选手不应通过非法方式获取评测器内部信息，例如直接与标准输入、标准输出流进行交互。此类行为将被视为作弊；
• 本题会受到和传统题相同的限制，例如编译错误会导致整道题得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分；
• 选手只能在程序中访问自己定义的变量以及评测器通过函数参数给出的变量，尝试访问其他地址空间可能导致编译错误或运行错误。

每次调用 starmap 函数时，若 report 函数或 rotate 函数调用不合法，或 rotate 函数调用次数超过 $p$ 次，则相应测试点得 $0$ 分。

在上述条件基础上：

• 对于每个测试点，若 report 函数报告的可行性正确，则可以获得 $25\%$ 的分数；
• 在此基础上，若对于每组可以达成条件的测试数据，所有仪式结束后均满足条件，则可以额外获得 $25\%$ 的分数；
• 在此基础上，若仪式次数均不超过 $nm$，则可以获得满分。

提交模板

#include "starmap.h"
#include <vector>

void init(int c, int t) {
    // 可在这里根据测试点编号 c 和数据组数 t 做初始化
}

void starmap(int n, int m, std::vector<std::vector<int>> a) {
    // 若认为无解：
    // report(false);

    // 若认为有解：
    // report(true);
    // rotate(...);
}