题目类型说明

这是一道提交函数题，不是传统的标准输入输出题。

你需要提交文件 crption.cpp，在其中实现评测程序要求的函数；不要自行编写 main 函数，也不要从标准输入读入或向标准输出写出任何内容。

题目描述

Iliyan 的城堡里有 $N$ 座高度互不相同的塔。一些塔之间用桥连接，并且满足一个重要性质：

若按高度从低到高排列这些塔，得到 $x_1,x_2,\dots,x_N$，那么对于每个 $1 \le i < N$，都一定存在一座桥连接 $x_i$ 与 $x_{i+1}$。

现在，图中的每条桥都被赋予了一个方向，方向总是应当从较低的塔指向较高的塔。

但是原始数据中出现了“腐败”：有恰好 $K$ 条桥的方向被错误记录了。

你的任务是通过尽量少的查询，恢复所有塔按高度从低到高的顺序。

你需要实现的函数

你需要实现如下函数：

vector<int> solve(const int &N, const vector<int> &from, const vector<int> &to);

它对每个测试只会被调用一次。

其中：

• N 是图中的顶点数；
• from 和 to 描述图中的有向边；
• 对于每个 $i<M$（$M$ 为边数），存在一条从 from[i] 指向 to[i] 的有向边；
• 顶点编号从 0 开始。

你的函数需要返回一个长度为 $N$ 的排列，表示所有塔按高度从低到高的顺序。

可用接口

你可以调用如下函数：

bool check(const int &from, const int &to);

它的含义是：检查初始图中从 from 指向 to 的这条边是否被“腐败”了。

• 当塔 from 实际上比塔 to 更高时，函数返回 true；
• 否则返回 false。

注意：

• 你最多只能调用 check 10^7 次；
• 如果你传入的 (from,to) 不是初始图中存在的边，程序会直接报错终止。

提交要求

你提交的文件必须为 crption.cpp，并满足：

• 文件中必须实现函数 solve；
• 可以包含其他辅助函数和所需代码；
• 不能包含 main 函数；
• 文件开头必须包含头文件：

#include "crption.h"

数据范围

• $N \le 10^5$
• $M \le \min\left(\dfrac{N(N-1)}{2}, 5 \times 10^5\right)$
• $K \le 20$

子任务

• 约 20% 的测试满足 $N \le 20$；
• 在其余测试中，$N \le 10^5$，并且：
  • 20% 的测试满足 $K \le 3$；
  • 56% 的测试满足 $K \le 5$；
  • 72% 的测试满足 $K \le 9$；
  • 100% 的测试满足 $K \le 20$。

评分方式

每个测试点单独计分。

• 如果返回的塔序不正确，则该测试得分为 $0$；
• 否则，设你的程序使用了 $q_s$ 次查询，则该测试得分为

$$\min\left(1.0, \left(\frac{2NK+1}{q_s+1}\right)^{3.75}\right)$$

本地测试

官方提供 Lgrader.cpp 与 crption.h 用于本地测试。

将它们与自己的 crption.cpp 放在同一目录下，并一同编译，即可得到本地测试程序。

本地测试程序从标准输入读取以下内容：

• 第一行：三个正整数 $N,M,K$，分别表示塔的数量、桥的数量和错误方向的数量；
• 第二行：一个排列 $x_1,\dots,x_N$，表示塔按高度从低到高的真实顺序；
• 接下来 $M$ 行：每行两个整数 $(a,b)$，表示在真实情况下塔 $a$ 比塔 $b$ 低，即边方向应为 $a \to b$；
• 最后 $K$ 行：每行一个边的编号，表示该边会被反向，从而制造一条“腐败”数据。

样例通信过程

你的程序动作	评测程序的响应
	solve(4, {0, 2, 3}, {2, 1, 1})
check(0, 2)	false
check(2, 1)
check(3, 1)	true
return {0, 2, 1, 3}

样例说明

在上述样例中，塔按高度从低到高的真实顺序为 $\{0,2,1,3\}$。

只有一条边被腐败（最后一条边），程序共进行了 $3$ 次查询，因此该测试获得的分数为：

$$\min\left(1.0, \left(\frac{2\times 4 \times 1 + 1}{3+1}\right)^{0.75}\right)=1.0$$