4360. 逆序排列

【题目背景】

排列铺就的，不止是关系

但只要有人问着，就不算逆序

【题目描述】

折枝 和 淮清 正在玩一个猜排列的游戏。

淮清 有一个 $1 \sim n$ 的排列 $p = [p_1, p_2, \dots, p_n]$。现在 折枝 知道了排列的长度 $n$，他希望通过特定的询问方式猜出这个排列 $p$。具体地，折枝 可以向 淮清 提出如下形式的询问：

给定整数 $l, r$ 满足 $1 \le l \le r \le n$，求区间 $p_l, \dots, p_r$ 中逆序对数量的奇偶性。

若存在下标 $i, j$ 满足 $l \le i < j \le r$ 且 $p_i > p_j$，则称其为一个逆序对。

为了增加游戏的难度，淮清 限制了 折枝 的询问次数。你需要帮助 折枝 还原出 淮清 的排列。

【实现细节】

选手不需要，也不应该实现 main 函数。

选手需要确保提交的程序包含头文件 inv.h，即在程序开头加入以下代码：

#include "inv.h"

选手需要在提交的程序源文件 inv.cpp 中实现以下两个函数：

void init(int c, int t);

$c, t$ 分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

对于每个测试点，该函数会在程序开始运行时被交互库调用恰好一次。

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

$n$ 表示排列的长度。

该函数需要返回一个长度为 $n$ 的 $1 \sim n$ 排列，表示 折枝 的猜测。

对于每个测试点，该函数会被交互库调用恰好 $t$ 次。

选手可以通过调用以下函数进行一次询问：

int query(int l, int r);

$l, r$ 表示询问的区间边界。选手需要保证 $1 \le l \le r \le n$。

该函数会返回区间 $[l, r]$ 逆序对总数的奇偶性（$0$ 为偶数，$1$ 为奇数）。

选手需要保证交互库每次调用 solve 时，调用该函数的次数不超过 $4 \times 10^4$。

注意：在任何情况下，最终测试时所用的交互库运行所需时间均不会超过 $0.1$ 秒，所用内存为固定大小，且均不超过 $64$ MiB。

【输入格式】

对于编译得到的可执行程序：

可执行文件将从标准输入读入以下格式的数据：

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号和测试数据组数。

接下来依次为每组测试数据，对于每组测试数据：

第一行包含一个正整数 $n$，表示排列的长度。

第二行包含 $n$ 个正整数 $p_1, p_2, \dots, p_n$，表示 淮清 的排列。

【输出格式】

对于每组测试数据：

第一行包含一个字符串，表示测试的结果。其中，

Correct 表示选手返回的结果正确；

Wrong answer 表示选手返回的结果错误；

Invalid operation 表示选手对 query 函数的调用不合法。

若结果为 Correct，则第二行包含一个非负整数，表示选手在所有测试数据中调用 query 函数的次数的最大值。

【样例 1 输入】

0 1
3
2 3 1

【样例 1 输出】

Correct.
3

【样例 1 解释】

该样例共包含一组测试数据。

对于第一组测试数据，淮清 的排列为 $p = [2, 3, 1]$。

以下是 折枝 的一种可能的交互过程：

调用 query(1, 2)，区间 $[2, 3]$ 逆序对数为 $0$，返回 $0$。

调用 query(2, 3)，区间 $[3, 1]$ 逆序对数为 $1$，返回 $1$。

调用 query(1, 3)，区间 $[2, 3, 1]$ 逆序对为 $(2, 1), (3, 1)$ 共 $2$ 个，返回 $0$。

返回 $q = [2, 3, 1]$。

大洋里

【数据规模与约定】

对于所有测试数据，均有：

$t = 10$；

$1 \le n \le 2000$；

$p$ 是 $1 \sim n$ 的一个排列。

测试点 $1 \sim 4$：$n \le 10$。

测试点 $5 \sim 8$：$n \le 500$，$p$ 随机生成。

测试点 $9 \sim 12$：$n \le 1000$，性质 A：$p$ 为单峰排列（先递增后递减）。

测试点 $13 \sim 20$：$n \le 2000$。

TEST

【评分方式】

注意：选手不应当通过非法方式获取交互库的内部信息。此类行为将被视为作弊。

每次调用 solve 函数时，若返回的排列不正确，或 query 函数调用不合法，则该测试点得 $0$ 分。

在上述条件基础上，设 $m$ 表示所有测试数据中调用 query 函数次数的最大值，则程序将获得该测试点分值的 $P(m)$ 倍分数，其中 $P(m)$ 的计算方式如下：

• 当 $m \le 40000$ 时，$P(m) = 1.0$；
• 当 $m > 40000$ 时，$P(m) = \frac{40000}{m}$。

注意：虽然询问次数超过 $4 \times 10^4$ 不会直接导致 Wrong answer，但会导致该测试点分数按比例折损。