题目描述

评测系统事先隐藏了一组由 0 到 N-1 组成的排列 π。你需要通过尽量少的询问把这个排列找出来。

可以把排列 π 看成一个函数：对于每个 m (0 ≤ m < N)，π(m) 表示排列中位置 m 上的数。

一次询问的方式如下：

你把数字 0,1,2,...,N-1 划分成 K 个非空集合（K 由你决定，也称为这次询问的大小）。记这些集合为：

• S_1, S_2, ..., S_K

要求每个数字恰好属于其中一个集合。

之后，对每个集合 S_i，评测系统把其中每个元素 x 都映射为 π(x)，从而得到集合 S_i'。更形式化地说，若：

$$S_i = \{a_i^1, a_i^2, \dots, a_i^{|S_i|}\}$$

那么：

$$S_i' = \{\pi(a_i^1), \pi(a_i^2), \dots, \pi(a_i^{|S_i|})\}$$

最后，评测系统会：

• 打乱每个 S_i' 内部元素的顺序；
• 再打乱这些 S_i' 集合之间的顺序；
• 然后把这个打乱后的结果返回给你。

例如，当 N = 5，π = [3,1,0,4,2] 时，如果你发出询问：

{{0, 3}, {4, 1, 2}}

那么一个可能的返回结果是：

{{1, 2, 0}, {3, 4}}

请编写程序 islands.cpp，在询问次数尽可能少的前提下，正确找出隐藏排列。题目还可能对单次询问的最大集合数 K 加以限制。

注： 整道题本来是发生在某些岛屿上的，但来不及补剧情了。

实现细节

你需要实现如下函数：

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

该函数只会被调用一次，参数 N 是排列长度。函数应返回长度为 N 的数组，即排列 π 本身。

评测器还提供函数：

std::vector<std::vector<int>> ask(const std::vector<std::vector<int>> &partition);

你可以调用它任意多次。其参数 partition 表示一次划分：

• partition 中的每个元素都是一个集合 S_i；
• 每个 S_i 又由若干整数构成。

顺序均不重要。

返回值与之格式相同，表示题面中定义的打乱后结果。再次强调：

• 每个返回集合内部是乱序的；
• 返回的各个集合之间的顺序也是乱序的。

你的程序：

• 必须实现 solve；
• 不能包含 main；
• 不能读标准输入，也不能写标准输出；
• 必须包含：

#include "islands.h"

在这些条件下，你可以自由使用辅助函数、变量、常量等。

限制

• 3 ≤ N ≤ 10^4
• 最多允许的询问次数：2 × 10^4
• 单次询问最大大小：SizeLimit（取决于子任务）

本地测试

你会得到 islands.h 和 Lgrader.cpp，可以与自己的程序一起编译测试。

程序启动后：

• 第一行输入 N；
• 第二行输入 N 个互不相同的整数，均在 0 到 N-1 之间，表示隐藏排列；
• 程序之后会输出：
  • 你的 solve 返回的排列；
  • 使用的询问次数；
  • 所发出询问中的最大大小。

子任务与评分

一个子任务的得分取决于其中所有测试的最差结果。

若在某个测试上：

• 你发出了非法询问；或
• 超过了询问次数限制；或
• 返回了错误排列；

则该测试得分为 0。

否则，该测试得分（0 到 1 之间）只取决于你发出的询问数 Q，计算公式为：

$$0.6^{\max(Q-Target,\ 0)}$$

其中 Target 由子任务决定。

子任务如下：

子任务	分值	N	SizeLimit	Target
1	11	= 15	N	15
2	15	= 4997		Opt(N) + 15
3		= 5000
4	17	= 5010		Opt(N) + 5
5	16	≤ 10^4		Opt(N)
6	9	= 8778	500
7	8	= 9889
8	9	≤ 10^4

其中，Opt(N) 表示对于给定 N，理论上可证明的最少询问次数。

样例通信

步骤	solve 的行为	评测器的动作 / 返回值
1	solve(3)
2	ask({{0}, {1, 2}})	return {{1, 2}, {0}}
3	ask({{2}, {1, 0}})	return {{1}, {0, 2}}
4	return {0, 2, 1}

说明

• N = 3
• π = {0, 2, 1}