P8303 [CoE R4 C] 网格

**这是一道交互题。** 有一张 $n$ 个点的无向无权图。 这张图有一个特殊性质：存在一个点 $u \ (1 \leq u \leq n)$ 到正整数对 $(x, y) \ (1 \leq x \leq l, 1 \leq y \leq c)$ 的**一一对应**关系，使得 $n = l \cdot c$，且点 $u, v$ 间存在边当且仅当 $u, v$ 对应的数对 $(x_u, y_u), (x_v, y_v)$ 满足 $|x_u - x_v| + |y_u - y_v| = 1$。换而言之，这张图和 $l$ 行 $c$ 列的网格图同构。 现在，你要通过一些询问还原这张图的结构。每次询问时，你需要给定一个点 $u \ (1 \leq u \leq n)$。询问的返回值是一个长为 $n$ 的数组 $\{d_i\} \ (1 \leq i \leq n)$，表示点 $u, i$ 间的最短路径所经过的边数。 请你使用不超过 $q$ 次询问，还原出这张图的结构。 --- ### 交互格式 **本题有多组数据。** 首先输入一个整数 $T$，表示数据组数。 对于每组数据： - 首先输入一个整数 $n$，表示图的点数。 - 接下来，你可以执行一些询问。对于每次询问，输出一个整数 $u$，为你询问的点。然后，输入 $n$ 个整数 $\{d_i\}$，为询问的返回值。 - 当你确定答案后，输出一个整数 $0$，然后输出答案。 在输出答案时： - 第一行输出两个整数 $l, c$； - 接下来，输出 $l$ 行 $c$ 列整数，为你还原的对应关系。第 $i$ 行 $j$ 列的数为 $(i, j)$ 对应的编号。 如果有多个答案，你可以输出任意一个。一个答案是正确的，当且仅当它和标准答案无法被任何询问区分：也就是，在这两个答案对应的网格图中，任意点对间的最短路径所经过的边数都是相同的。 --- 请注意：**在每次执行询问或者输出答案后，你应该清空缓冲区：** - 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 - 在 Java 中，使用 `System.out.flush()`。 - 在 Python 中，使用 `stdout.flush()`。 - 在 Pascal 中，使用 `flush(output)`。 - 对于其他语言，请自行查阅对应语言的帮助文档。

无

无

### 样例 $1$ 解释 对于样例，以下 $3$ 行 $2$ 列的网格图也是正确的输出。 ``` 3 2 4 2 3 5 6 1 ``` 左边是样例对应的网格图，右边是以上输出对应的网格图。  --- ### 评分标准 对于一个子任务，令 $q_{\max}$ 为你在这个子任务的所有测试数据中的最大询问次数。 如果交互的格式不合法，运行超出了时间限制，或者你的答案不正确，或者 $q_{\max} > q$，你的得分为 $0$。 否则，对于子任务 $1 \sim 3$，你得满分；对于子任务 $4$，你的分数由下表给出： | 条件 | 分数 | | :-: | :-: | | $q_{\max} \leq 3$ | $61$ | | $q_{\max} = 4$ | $41$ | | $q_{\max} = 5$ | $31$ | | $q_{\max} = 6$ | $21$ | | $q_{\max} \geq 7$ | $11$ | --- ### 数据规模 **本题采用捆绑测试。** | 子任务 | 分值 | $n \leq$ | $q = $ | 特殊性质 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $3$ | $4$ | $4$ | 无 | | $2$ | $13$ | $10^5$ | $4$ | 存在解使得 $l = 1$ | | $3$ | $23$ | $36$ | $36$ | 存在解使得 $2 \leq l, c \leq 6$ | | $4$ | $61$ | $10^5$ | $12$ | 无 | 对于所有数据，保证 $1 \leq T \leq 10^3$，$1 \leq n \leq 10^5$，$\sum n \leq 3 \times 10^5$。 在部分测试数据中，交互器是自适应的。也就是，图的结构可能会根据你的询问而变化。但是可以保证：在每次询问之后，存在至少一个答案符合当前所有询问的返回值。