注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "permutation.h"。

题目描述

题目译自 Romanian Master of Informatics 2019 Day2 T2 「Secret Permutation」

有一个包含 $1$ 到 $N$ $(3 \leq N \leq 256)$ 的所有整数的隐藏排列 $P$。你需要找到这个排列。排列 $P$ 是固定的，即评测程序不是自适应的。

在你的程序中，你可以询问另外一个排列 $V$ 的值：

• $\texttt{Query(V)}$ 将返回 $\sum\limits_{i=1}^{N-1} |P[V[i]] - P[V[i + 1]|$ 的结果。

通过执行一定数量的查询，你需要找到排列 $P$，或者任何另一个与 $P$ 不可区分的排列 $P^{\prime}$。如果在所有可能的查询中，两种排列给出的答案相同，则认为它们是不可区分的。

交互方式

你需要实现以下函数：

void solve(int N);

• 你需要在此函数中实现你的程序。

void answer(std::vector<int> P);

• 当你已经确定排列 $P$ 时，请你将排列 $P$ 作为参数调用此函数。调用此函数将终止程序。

你可以调用以下函数：

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

• 你可以通过调用此函数并传入一个包含从 $1$ 到 $N$ 的所有整数的排列 $V$ 作为参数来执行查询。你的分数将基于你调用此函数的次数。

样例

#include "permutation.h"
void solve(int N) {
  if (N == 2) {
    std::vector<int> V = {1, 2};
    int qAns = query(V);
    if (qAns == 1) {
      std::vector<int> P = {1, 2};
      answer(P);
    }
  }
}

样例评测程序

你可以从「文件」下载两个文件进行本地测试：sample_grader.cpp 和 permutation.h。

样例评测程序会从标准输入读取一个整数 $N$，表示隐藏排列的大小，接下来读入 $N$ 个不同的整数，表示隐藏的排列 $P$。然后，评测程序会调用你实现的 solve() 函数。

评测程序会输出以下信息到标准输出中：

• 每次 query() 调用的结果：查询的排列和查询的结果；
• 每次 answer() 调用的结果：判断（正确或错误答案）、$N$ 和你使用的查询次数。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$15$	$3 \leq N \leq 7$
$2$	$35$	$3 \leq N \leq 50$
$3$	$50$	$3 \leq N \leq 256$

每个测试数据的分数按如下规则计算：

如果你没能找到正确的排列之一，那么得分为 $0 \%$。否则，设 $Q$ 为找出排列 $P$ 所需的查询次数。

• 如果 $Q \leq N$ 则得分为 $100 \%$。
• 如果 $N \leq Q \leq 2N$ 则得分为 $(100 - 40\times \frac{Q-N}{N}) \%$。
• 如果 $2N \leq Q \leq N^2$ 则得分为 $(60 - 40 \times \frac{Q - 2N}{N^{2}-2N}) \%$。
• 如果 $N^{2} \leq Q$ 则得分为 $20 \%$。

该任务的总分将四舍五入到小数点后两位。