排列游戏（perm）

项目	说明
题目类型	函数提交题 / 离线交互题
时间限制	5 秒
空间限制	512 MB
提交语言	C++
评测方式	特殊评测

提交说明

本题不是传统输入输出题，而是 函数提交题。

你只需要提交一个 C++ 源文件，实现如下函数：

#include "perm.h"
#include <vector>

std::vector<int> solve(int id, int n) {
    // 在这里编写你的程序
}

请注意：

• 不要编写 main() 函数；
• 不要从标准输入读取数据；
• 不要向标准输出输出任何内容；
• 系统评测时会自动将你的程序与官方 grader.cc 和 perm.h 一起编译；
• 如果你输出调试信息，可能会影响特殊评测结果。

题目描述

交互库中有一个隐藏的 $1$ 到 $n$ 的排列 $p$。

每次询问时，你可以给出两个整数 $u,v$，满足 $1\le u,v\le n$。交互库会返回 $u$ 与 $v$ 在隐藏排列中的位置距离对 $3$ 取模的结果。

也就是说，若 $p_i=u$，$p_j=v$，则询问返回：

$$|i-j|\bmod 3$$

你需要在询问次数限制内求出隐藏排列 $p$。

保证排列的生成方式为：确定长度 $n$ 后，在所有满足子任务限制，且满足 $p_1<p_n$ 的排列中等概率随机生成一个。

接口说明

你需要包含头文件：

#include "perm.h"

该头文件中声明了如下接口：

std::vector<int> solve(int id, int n);
int query(int u, int v);

需要你实现的函数

std::vector<int> solve(int id, int n);

参数含义如下：

• id：当前测试点所属的子任务编号；
• n：隐藏排列的长度。

你需要返回一个长度为 $n$ 的 std::vector<int>，表示你求出的排列。

返回值必须满足：

• 长度恰好为 $n$；
• 是 $1$ 到 $n$ 的一个排列；
• 顺序必须与隐藏排列完全一致。

该函数在每个测试点中会被调用恰好一次。

可以调用的函数

int query(int u, int v);

参数含义如下：

• u,v：你要询问的两个值。

你必须保证：

$$1\le u,v\le n$$

若 $p_i=u$，$p_j=v$，则该函数返回：

$$|i-j|\bmod 3$$

如果询问参数非法，或询问次数超过限制，该测试点将被判为错误。

输入格式

本题为函数提交题，选手程序不需要从标准输入读取任何数据。

测试数据由官方评测程序读取。评测程序会将 id 和 n 作为参数传入你实现的 solve(id,n) 函数。

输出格式

选手程序不需要向标准输出输出任何内容。

你只需要在 solve(id,n) 中返回你求出的排列。

询问限制

每个测试点最多允许调用：

$$4\times 10^5$$

次 query。

数据范围与子任务

本题开启捆绑测试。

对于所有测试数据，保证：

$$3\le n\le 10^4$$

子任务编号	分值	限制
$1$	$5$	$n=3$
$2$		$n\le 850$
$3$	$10$	$n\le 1050$
$4$		$n\le 5000$
$5$	$30$	保证 $p_1=1$
$6$	$40$	无特殊限制

评分方式

本题首先受到与传统题相同的限制。若你的程序在运行过程中出现以下情况，则对应测试点得 $0$ 分：

• 运行超时；
• 内存超限；
• 运行错误；
• 返回的排列错误；
• 返回值非法；
• 询问次数超过 $4\times 10^5$；
• 询问参数不满足 $1\le u,v\le n$。

保证每个子任务的测试点数量不超过 $10$ 个。

对于子任务 $1$ 到 $4$，若你的答案正确，则可获得该测试点满分。

对于子任务 $5$ 到 $6$，设你的询问次数为 $c$，令：

$$k=\frac{c}{n}$$

则该测试点得分比例按如下方式计算：

条件	得分比例
$k>40$	$0$
$25\le k\le 40$	$\dfrac{1}{75}(40-k)$
$20\le k\le 25$	$\dfrac{2}{25}(25-k)+\dfrac{1}{5}$
$14<k\le 20$	$\dfrac{1}{15}(20-k)+\dfrac{3}{5}$
$k\le 14$	$1$

在 $k=25,22.5,20,17,14$ 时，你分别可以获得 $20\%,40\%,60\%,80\%,100\%$ 的分数。

本地测试说明

压缩包中的样例输入只用于官方 grader 本地测试，不是选手程序需要直接读取的输入。

例如，某个本地测试文件可能为：

0 3
1 2 3

其含义是：

• 子任务编号 id=0；
• 排列长度 n=3；
• 隐藏排列为 [1,2,3]。

在 Hydro 上提交时，你不需要处理这种输入格式，只需要实现 solve(id,n)。

提交代码示例

下面的代码只展示提交结构，不保证可以通过本题：

#include "perm.h"
#include <vector>
using namespace std;

vector<int> solve(int id, int n) {
    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        ans.push_back(i);
    }
    return ans;
}