注意事项

提交的文件必须包含 #include "permutation.h"。

题目描述

吉米（Gimi）陷入了一个相当复杂的境地！

他发现了一台旧机器。机器内部有 $N$ 个隐藏的开关 $s[0], s[1], s[2], \ldots, s[N-1]$。任何开关 $i$ 都可以处于关闭状态（用 $s[i]=0$ 表示）或开启状态（用 $s[i]=1$ 表示）。最初，所有开关都是关闭的。机器上还有从 $0$ 到 $N-1$ 编号的 $N$ 个按钮，一个屏幕，以及一个由数字 $0, 1, 2, \ldots, N-1$ 组成的秘密排列 $P = p[0], p[1], p[2], \ldots, p[N-1]$。

机器上的一张大海报写着：「如果你能猜出排列 $P$，你就能赢得大奖！」现在吉米想要这个奖品，所以他请求你的帮助。

为了确定 $P$，你可以按下机器上的按钮。当你按下第 $i$ 个按钮时，会发生以下情况：

1. 令 $k$ 为在此之前你按下任意按钮的总次数。
2. 编号为 $p[k \% N]$ 的开关会被翻转（形式化地讲，$s[p[k \% N]] := 1 - s[p[k \% N]]$）；
3. 屏幕显示编号为 $i$ 的开关的当前状态（即 $s[i]$ 的值）。

给你整数 $N$。你必须通过按动机器的按钮足够少的次数来确定隐藏的排列 $P$。

由于机器很旧，如果你按按钮次数过多，它会坏掉。因此，如果按钮被按下的次数超过 $50 \cdot N$ 次，你将无法获得奖品。

出于同样的原因，你希望最小化按按钮的总次数。关于更详细的限制，请参阅「数据范围与提示」部分。

实现细节

提交的文件必须包含 #include "permutation.h"。

你应该实现以下函数：

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

该函数接收 $N$ 作为参数，并且必须返回一个大小为 $N$ 的向量 $q$，使得对于每个 $0 \leq i \leq N-1$，都有 $q[i]=p[i]$。对于每个测试用例，该函数恰好被调用一次。

在你的解决方案中，你可以调用函数：

int press_button(int i);

该函数返回按下第 $i$ 个按钮的结果，即上述步骤 2 和 3 之后 $s[i]$ 的值。

样例

考虑一个 $N=4$ 且 $P=[1,3,0,2]$ 的样例，以及以下对 press_button() 的调用示例。

操作	$S$ (当前开关状态)	返回值
press_button(0)	0100
		0
press_button(1)	0101
		1
press_button(2)	1101
		0
press_button(3)	1111
		1
press_button(1)	1011
		0
press_button(3)	1010
		0
press_button(2)	0010
		1
return {1,3,0,2}

数据范围与提示

对于所有输入数据，满足：

• $N \leq 10^{4}$
• $P$ 是数字 $0, 1, 2, \ldots, N-1$ 的一个排列。

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

子任务	分值	附加限制
$1$	$20$	$N=32$
$2$	$40$	$N=1000$
$3$	$40$	$N=10000$

每个测试用例的评分如下：令 $K$ 为你的解决方案调用函数 press_button() 的次数。令 $Q=\frac{K}{N}$。如果排列猜错了，或者 $Q>50$，则得分为 $0$。否则，得分为 $S$ 乘以该组的最高分，其中 $S$ 定义如下：

第 1 组：

$$S= \begin{cases}1, & Q \leq 7 \\ 1-\frac{1}{10}(Q-7), & 7<Q \leq 12 \\ \frac{1}{2}-\frac{1}{100}(Q-12), & 12<Q \leq 32 \\ \frac{3}{10}-\frac{1}{10} \sqrt[4]{\frac{Q-32}{18}}, & 32<Q \leq 50\end{cases}$$

第 2 组：

$$S= \begin{cases}1, & Q \leq 13 \\ \frac{1}{2}+\frac{1}{2}\left(\frac{23-Q}{10}\right)^{2}, & 13<Q \leq 23 \\ \frac{1}{5}+\frac{3}{10} \sqrt{\frac{50-Q}{27}}, & 23<Q \leq 50\end{cases}$$

第 3 组：

$$S= \begin{cases}1, & Q \leq 17 \\ \frac{3}{5}+\frac{25-Q}{20}, & 17<Q \leq 25 \\ \frac{1}{5}+\frac{2}{5}\left(\frac{50-Q}{25}\right)^{2}, & 25<Q \leq 50\end{cases}$$

示例评测程序

提供了一个示例评测程序 (sample-grader.cpp)。

评测程序按以下格式读取输入：

• 第 $1$ 行：整数 $N$
• 第 $2$ 行：$N$ 个整数 $p[0], p[1], p[2], \ldots, p[N-1]$。

然后它调用函数 solve(N) 并输出你的解决方案的裁决结果以及使用的查询次数或失败原因的解释。