UOJ Logo Universal Online Judge

UOJ

#721. 【UER #10】重构元宇宙 加强版

附件下载 统计

本题与 #707. 【UER #10】重构元宇宙 的差异仅有数据范围与 query 函数的返回值类型。

这是一道交互题。

在表彰大会上,码王 skip 蚤分享起了他最得意的一次用代码拯救世界的经历,只不过这个世界是虚拟世界。

跳蚤国有一个自主研发的元宇宙平台 —— 蚤宇宙。虽然现实世界只有三维,但在蚤宇宙,你可以体验到 $k$ 维空间的极致体验!

蚤宇宙里面共有 $n$ 个物体,编号为 $0$ 到 $n - 1$,其中每个物体的位置可以用一个 $k$ 维空间中的坐标表示。

然而在一个雨夜,一道闪电划破夜空,劈到了位于跳蚤利亚的蚤宇宙核心数据中心,引发了一场大火,无数的蚤宇宙数据化为焦土。

所幸在一个蚤宇宙数据备份中心里恰巧存储了这 $n$ 个物体两两之间的欧几里得距离。即,如果有两个物体的位置分别为 $(x_0, x_1, \dots, x_{k-1}) \in \mathbb{R}^k$ 和 $(x'_0, x'_1, \dots, x'_{k-1}) \in \mathbb{R}^k$,那么它们之间的距离就是 $d(x, x') = \sqrt{\sum_{i=0}^{k-1} (x_i - x'_i)^2}$。

“没有人比我更懂怎么重构元宇宙”,码王激动地说道。那晚,码王通过这些数据,还原出了一组合法的物体坐标,成为了蚤宇宙的英雄。虽然和原坐标不一定一样,但他们两两之间点的距离与备份中心里的记录完全一致。

坐在台下的你想要挑战码王!你不仅想解决相同的问题,还想只使用一部分备份中心存储的距离数据,来达到相同的目的。

任务

本题仅支持符合 C++ 11 标准及以上的 C++ 语言。

你必须引用 distance.h

你需要实现下面的过程:

std::vector<std::vector<double>> solve(int n, int k, int lim);

这个过程会被恰好调用一次。

$n$ 表示点的个数(即物体的个数),$k$ 表示空间维数,$\mathrm{lim}$ 表示你能使用 query 次数的上限。

你需要返回一个长度为 $n$ 的数组,元素是一个长度为 $k$ 的实数向量,表示每个点的坐标。

你可以调用以下函数:

double query(int a, int b);

你需要保证 $a,b\in[0, n)$。

这个函数会返回 $a$ 号点和 $b$ 号点欧几里得距离的平方

具体地,设 $a$ 号点坐标为 $(x_0,x_1,\ldots,x_{k-1})$,$b$ 号点坐标为 $(x'_0,x'_1,\ldots,x'_{k-1})$,则函数会返回:$d(x, x')^2 = \sum_{i=0}^{k-1}\left(x_i-x'_i\right)^2$。

这个函数至多被调用 $\mathrm{lim}$ 次。

评测方式

设 $D^2$ 为原始数据点中每一维坐标的极差的平方和,若对于任意 $i,j\in[0,n)$,返回的 $i$ 号点和 $j$ 号点欧几里得距离为 $\mathrm{out}$,输入的 $i$ 号点和 $j$ 号点距离为 $\mathrm{ans}$,均有 $\frac{|\mathrm{out}-\mathrm{ans}|}{\max\{1,D\} } \le 10^{-6}$,则你的返回结果将被判定为正确。

样例评测库将读入如下格式的输入数据:

第一行三个整数 $n,k,\mathrm{lim}$。

接下来 $n$ 行,每行 $k$ 个实数表示点的坐标。

样例评测库将输出如下格式的输出数据:

如果你的返回结果错误或交互过程不合法,则评测库会输出 WA 并输出错误原因。

否则输出两行,第一行为 OK,第二行输出你使用 query 的次数。

交互式类型的题目怎么本地测试

最终测试中,点坐标是确定的,不会因为你的询问而改变,并且最终评测库与下发评测库仅有反作弊上的差别。

样例一

input

3 2 9
0 0
0 1
1 0

output

OK
query count: 9

explanation

你可以询问出所有点对间的距离。

query 的返回值如下

$~$ $0$ $1$ $2$
$0$ $0$ $1$ $1$
$1$ $1$ $0$ $2$
$2$ $1$ $2$ $0$

合法的返回值并不唯一,一组合法的返回是:$(1,1),(0,1),(1,0)$。

样例二

见附件下载中的 ex_distance2.inex_distance2.ans

数据范围与提示

子任务编号 $n\leq$ $k\leq$ $\mathrm{lim}\geq$ 分值
$1$ $3$ $n$ $n(k+1)$ $20$
$2$ $500$ $1$ $n(k+1)$ $20$
$3$ $100$ $n$ $n^2$ $20$
$4$ $100$ $n$ $n(k+1)$ $10$
$5$ $500$ $n$ $n(k+1)$ $30$

对于所有数据,保证 $1\leq k\leq n\leq 500,n(k+1)\leq \mathrm{lim}\leq 250500$,点的坐标均为 $[-500,500]$ 内的实数。

保证合法的交互过程中,交互库不会使用超过 $\texttt{0.5s}$ 的时间和 $\texttt{64MB}$ 的空间。

hack

hack 数据的格式与样例输入数据一致,实数的小数部分不得超过 $10$ 位。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$