题目描述

题目译自 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\%$。