T686510 [CFCOI-R3.5-T1] 猜数(guess)

:::info[题目信息] - 出题人：[Hamburger999](https://www.luogu.com.cn/user/1045301) - 数据：[Hamburger999](https://www.luogu.com.cn/user/1045301) Hint: 此题就是题目描述长，并不难。 $\text{guess.cpp},1 \text{ s},512 \text{ MiB}$ ::: **这是一道交互题。** 你可以在下面 $0 \ \text{pts}$ 示例程序中编辑： ```cpp #include using namespace std; extern "C" vector init(int n){ return {}; } extern "C" vector guess(int n,vector b){ return {}; } ```

小 A 和小 B 正在玩游戏。 小 A 有一个长度为 $n$ 的整数序列 $a_0,a_1,\cdots,a_{n-1}$。小 B 不知道这个序列。 小 A 将 $a$ 序列复制了一份得到 $b$ 序列。然后小 B 最多可以进行 $k$ 次操作，第 $i$ 次操作选择 $x_i,y_i$，然后小 A 会将 $b_{y_i}$ 减去 $a_{x_i}$。 小 B 的操作需要保证： + 对于 $0 \le i < n$ 的每个整数 $i$，至少存在一个 $j$ 使得 $x_j=i$。 + 对于 $0 \le i < n$ 的每个整数 $i$，至少存在一个 $k$ 使得 $y_k=i$。 最后小 A 会告诉小 B 最终的 $b$ 序列，你要扮演小 B 的角色进行操作，并根据最终的 $b$ 序列还原 $a$ 序列。 #### 交互说明 你需要实现函数 `std::vector init(int n)`： 该函数接收 $1$ 个整数 $n$，返回小 B 的操作序列。该序列由若干个二元组 $(x_i,y_i)$ 组成。这个序列的长度应当不超过 $k$。 你需要实现函数 `std::vector guess(int n,std::vector b)`： 这个函数接收小 B 收到的 $1$ 个整数 $n$ 和最终的 $b$ 序列，你应当返回你求出的 $a$ 序列。 你不应该，也无需实现主函数。

你无法读入输入文件。 输入文件包含 $2$ 个整数 $n,k$。序列 $a$ 将在程序内部均匀随机生成。

你无需实现主函数，也无需有任何输出。

#### 一个可能的交互过程 交互库接收到 $n=1,k=2$，初始化 $a=\{233\}$。调用 `init(1)`。返回值为 `{{0,0}}`。 交互库检查操作序列的合法性。这个操作序列合法。 交互库按照操作序列操作，得到序列 $b=\{0\}$。 交互库调用 `guess(1,{0})`，由于你的运气好，恰好返回了 `{233}`。 这个返回的序列与 $a$ 相同，你通过了这个测试点。 #### 数据范围 对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^5,|a_i| \le 10^5,k \ge n+1$。 本题共 $10$ 个测试点，测试点数据范围如下： ::cute-table{tuack} | 测试点编号 | $n=$ | $k=$ | |:-:|:-:|:-:| | $1$ | $1$ | $2$ | | $2 \sim 4$ | $3 \times 10^5$ | $2n$ | | $5 \sim 10$ | ^ | $n+1$ | #### 评分方式 如果生成的操作序列长度 $>k$ 或者不符合题目要求，得 $0$ 分。 如果还原的 $a$ 序列不正确，得 $0$ 分。 如果操作序列符合要求并且还原的 $a$ 序列正确，得满分。