CK2. 礼物（Present）

题目描述

隐藏着一个由 $1$ 到 $N$ 组成的排列 $a_1,a_2,\ldots,a_N$。你需要通过询问恢复整个排列。

你可以向评测程序提出如下询问：给定两个整数 $x,k$，询问隐藏排列前 $x$ 个数中的第 $k$ 小值。

也就是说，question(x, k) 返回一个数 $v$，它在集合

中恰好比 $k-1$ 个数大。

你可以自由选择 $x$ 和 $k$，但必须满足：

如果调用 question 时参数不满足上述条件，该测试点将被判为 Wrong Answer。

实现要求

本题是函数式提交题。你需要提交一个 C++ 源文件，文件中实现如下函数：

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

评测程序会调用一次 solve(N)，其中 $N$ 为隐藏排列长度。你需要返回一个长度为 $N$ 的 vector<int>，依次表示恢复出的排列：

{a_1, a_2, ..., a_N}

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

int question(int x, int k);

它返回隐藏排列前 $x$ 个数中的第 $k$ 小值。

你的提交文件必须包含头文件：

#include "present.h"

你的程序：

• 不需要也不允许实现 main 函数；
• 不要从标准输入读入；
• 不要向标准输出输出；
• 只需要实现 solve 函数，可以自行编写辅助函数和全局变量。

数据范围

隐藏排列满足：

且当 $i\ne j$ 时，$a_i\ne a_j$。

question(x,k) 的复杂度为 $O(\log N)$。调用次数没有显式限制，但你的程序需要在时限内完成。

子任务

只有当某个子任务及其依赖子任务全部通过时，才能获得该子任务分数。

本地测试说明

原题提供了 present.h 和 Lgrader.cpp 用于本地测试。将你的 present.cpp 与这两个文件放在同一目录下，只编译 Lgrader.cpp 即可。

本地测试程序输入格式为：

第一行一个整数 $N$。
第二行 $N$ 个整数，表示隐藏排列。

本地测试程序会调用你的 solve 函数，并输出你的函数返回的排列。

示例交互

假设隐藏排列为：

3 1 2

一种可能的交互过程如下：

@头文件下发