СK12. Sums / 求和

题目描述

近年来，信息学竞赛中的交互题明显变少了，于是 Kircho 决定给你出一道这样的题。

给定一个正整数 $N$，有 $N$ 枚硬币，面值分别为 $1,2,\ldots,N$，每种面值各一枚。Kircho 事先想好了这些硬币的一个隐藏排列：

$$a_0,a_1,\ldots,a_{N-1},$$

然后把每枚硬币翻过来，使你看不到它们的面值。你的目标是确定整个排列。

你可以向 Kircho 询问若干问题。每次询问给出一个下标集合 $P=\{P_0,P_1,\ldots,P_{K-1}\}\subseteq \{0,1,\ldots,N-1\}$，询问这些位置上的硬币所能组成的子集和中，最小的不能表示出的正整数是多少。

注意，每枚硬币最多只能使用一次。

为了使问题不至于太简单，Kircho 又加了一个限制：如果这个最小不能表示出的正整数大于 $N$，他不会告诉你具体数值，而是返回 $0$。

形式化地，函数 query(P) 的返回值为：

$$\operatorname{query}(P)= \begin{cases} \text{集合 }\{a_{P_0},a_{P_1},\ldots,a_{P_{K-1}}\}\text{ 的子集和不能表示出的最小正整数}, & \text{若该值}\le N,\\ 0, & \text{否则。} \end{cases}$$

你不仅需要正确恢复隐藏排列，还应尽量减少询问次数。

实现要求

本题为函数式交互题。选手程序不通过标准输入输出与评测程序交互，而是通过给定函数交互。

你需要实现如下函数：

std::vector<int> solve(int N);

该函数会对当前测试文件中的每个子测试调用一次。函数需要返回一个长度为 $N$ 的向量，表示隐藏排列 $a_0,a_1,\ldots,a_{N-1}$。也就是说，返回向量的第 $i$ 个元素应为 $a_i$。

在 solve 中，你可以调用：

int query(std::vector<int> P);

一次 query(P) 表示向评测程序询问下标集合 $P$。为了使询问合法，$P$ 必须满足：

• $P_i \ne P_j$，对于任意 $i\ne j$；
• $0\le P_i<N$，对于所有 $i$。

评测程序中一次询问的复杂度为 $O(K\log^2 K)$，其中 $K=|P|$。

提交格式

你应提交一个 C++ 源文件，实现 solve 函数。文件开头需要包含：

#include "sums.h"

在本 Hydro OJ 配置中，选手代码末尾还应包含：

#include "grader.cpp"

请不要自己编写 main 函数。

推荐模板：

#include "sums.h"
using namespace std;

vector<int> solve(int N) {
    // 在这里实现你的算法，可以调用 query(...)
    return vector<int>();
}

#include "grader.cpp"

约束条件

• $T=5$，每个测试文件包含 $5$ 个子测试；
• $1\le N\le 1000$；
• $1\le a_i\le N$；
• $a_i\ne a_j$，对于 $i\ne j$。

子任务

子任务	分值	限制
1	6	$N=3$
2	31	$N=70$
3	63	$N=1000$

某个子任务的分数只会在该子任务的所有测试点均通过时获得；每个测试点还会根据询问次数给出比例分。

计分方式

若出现以下任意情况，则该测试点得 $0$ 分：

• 返回的排列不正确；
• 调用了非法询问；
• 在一个测试文件内总询问次数超过 $10^7$。

否则该测试点视为有效。设 $Q$ 为该测试文件中所有 $T$ 个子测试的总询问次数，$Q_{author}=26000$。该测试点获得的比例分为：

$$1-\sqrt{1-\min\left(1,\frac{Q_{author}}{Q}\right)^{0.6}}.$$

询问次数越少，得分越高。当 $Q\le 26000$ 时，该测试点可获得满分比例。

样例通信

下面给出一个 $N=2$ 的可能交互过程：

步骤	评测程序动作	选手程序动作
1	solve(2)	query({0})
2	返回 1	query({0, 1})
3	返回 0	return {2, 1};

本地测试

原包中提供了 sums.h 和 Lgrader.cpp，可用于本地测试。注意本地 grader 中的 query 与正式 grader 实现不同，本地版本的复杂度为 $O(2^K)$，因此只适合小数据调试。

本地 grader 输入格式：

第一行输入两个正整数 $N,T$。

接下来 $T$ 行，每行输入 $N$ 个整数，表示一个子测试中的隐藏排列。

本地 grader 会输出测试是否有效，以及有效时使用的总询问次数。

@下发文件