题目描述

Alice 又一次来到镜中世界，这次她需要帮 Humpty-Dumpty 整理一些掉落的点。

有 $N$ 个 $K$ 维点，编号为 $0$ 到 $N-1$。对于点 $i$，其第 $d$ 维坐标为 $X_{i,d}$（其中 $0 \le d < K$）。满足：

• 对于每一维 $d$，序列

  $$X_{0,d}, X_{1,d}, \dots, X_{N-1,d}$$

  恰好是 $0$ 到 $N-1$ 的一个排列；

• 各维的排列彼此独立，且都是等概率随机生成的。

Alice 可以进行如下操作：一次选择两个不同的点 $i,j$，然后同时得到它们在所有维度上的比较结果。也就是说，她会得到一个长度为 $K$ 的布尔数组，其中第 $d$ 个值为：

• true（或 1），若 $X_{i,d} < X_{j,d}$；
• false（或 0），否则。

Alice 的目标是通过尽量少的比较，恢复所有点在所有维度上的坐标，即求出全部的 $X_{i,d}$。

实现细节

你需要实现如下函数：

std::vector<std::vector<int>> pointSort(int n, int k);

评测程序会用相同的 $N$ 和 $K$ 调用该函数 $T$ 次，每次调用对应一个独立子测试。

你的函数应返回所有点的坐标，返回值按“先点编号、后维度编号”进行索引。

你可以调用评测程序提供的函数：

std::vector<bool> compare(int i, int j);

该函数可以被调用任意多次，但要求：

• $i$ 和 $j$ 必须是不同的合法点编号。

函数返回一个长度为 $K$ 的布尔数组，表示这两个点在每个维度上的大小关系。

额外要求

你的程序必须：

• 包含头文件 pointsort.h
• 不能定义 main 函数
• 不能从标准输入读取
• 不能向标准输出写出

约束条件

• $N = 10^4$
• $2 \le K \le 5$
• $6 \le T \le 15$

本地测试

题目提供了头文件和本地 grader，可与你的程序一起编译测试。

输入格式如下：

• 第一行输入 $T, N, K$
• 接着输入一个整数：
  • 1 表示让本地 grader 随机生成测试数据；
  • 0 表示你将手动输入测试数据。
• 对于每个子测试：
  • 若处于模式 1，输入一个整数，表示随机种子；
  • 若处于模式 0，输入 $N$ 行，每行 $K$ 个整数，表示各点坐标。

程序会输出每个子测试平均使用的比较次数，或者在出错时输出错误信息。

评分方式

本题共有 $4$ 个测试组，每组单独计分。

若程序进行了非法比较，或返回了错误答案，则该测试组得分为 $0$。

否则，记：

• $Q$ 为程序在 $T$ 次执行中，平均每个子测试使用的比较次数
• $Q^\*$ 为该测试组的目标比较次数

若 $Q \le Q^\*$，则该测试组得满分（比例得分为 $1$）。

否则定义相对额外比较次数：

$$E = \frac{Q}{Q^\*} - 1$$

得分比例 $S$ 为：

$$S = \max\left(1 - 3.75 \times \min(E, 0.15) - \max(E - 0.15, 0),\ 0.1\right)$$

下面给出若干 $E$ 与得分比例 $S$ 的对应关系：

$E$	$S$
0.00	100.00%
0.05	81.25%
0.10	62.50%
0.15	43.75%
0.20	38.75%
0.30	28.75%
0.40	18.75%
0.50	10.00%

测试组

测试组	分值	$K$	$T$	$Q^\*$
1	25	2	15	187500
2	35	3	10	267000
3	25	4	8	350800
4	15	5	6	434500