#299. 【NFLSPC #1】Permutation

题目类型:交互型 时间限制:1500 ms 空间限制:512 MiB
输入文件:N/A 输出文件:N/A 答案检查器:文本比较

本题为交互题,且仅支持 C++ 语言。请各位选手在提交时务必选择 C++11 及以上版本,否则可能无法编译通过。

题目描述

AobBlice 又在玩游戏。

Aob 是一个热爱思考的小朋友,所以他想了 $m$ 对数字。这些数字中的第 $i$ 对为 $x_i,y_i$,保证 $x_i,y_i\in [0,n)\cap \mathbb Z$。

Aob 是一个完美主义者。他认为一个 $\{0,1,\cdots,n-1\}$ 的排列 $p$ 是优美的,当且仅当 $\forall 1\le i\le m$,均有 $p_{x_i}\lt p_{y_i}$。

Aob 是一个热爱分享的小朋友,所以他想让 Blice 也知道这些数字。但是他不想直接告诉 Blice 这些数字,而是让 Blice 猜出这些数字。所以他让 Blice 提出若干问题,他来回答,从而帮助 Blice 猜出这些数字。

Aob 规定,每次提问时,Blice 可以问一个 $\{0,1,\cdots,n-1\}$ 的排列,而 Aob 会告诉 Blice 这个排列是否是优美的。由于 Aob 时间有限,所以 Blice 只能提出不超过 $10^5$ 个问题。

可是 Blice 觉得这太难了,于是 Aob 决定给他一个提示:一个优美的排列 $a$。另外,Aob 为了降低难度,决定只要 Blice 求出优美的排列中,字典序最小的那个即可。

可是 Blice 还是不会,于是他向你求助,请你帮帮他。

形式化的题目描述

记 $S=\{0,1,\cdots,n-1\}$。

初始时,评测机会生成一个 $S$ 的排列 $a$,以及 $m$ 对 $(x_i,y_i)$。保证 $\forall 1\le i\le m,a_{x_i}\lt a_{y_i}$。

选手(也就是你)将会得到这个 $a$。你可以做出若干询问,每次询问给出一个 $S$ 的排列 $q$。评测机会回答:这个 $q$ 是否满足 $\forall 1\le i\le m,q_{x_i}\lt q_{y_i}$。

你需要在不超过 $10^5$ 次询问后求出:$\min \{a\mid a\ 为\ S\ 的排列;\forall 1\le i\le m,a_{x_i}\lt y_i\}$。

定义一个排列 $p$ 比另一个排列 $q$ 小,当且仅当存在 $0\le i\lt n$(这里数组下标从 $0$ 开始),使得:$\forall 0\le j\lt i,p_j=q_j$ 且 $p_i\lt q_i$。

实现细节

本题为一道交互题。因本题交互数据量十分巨大,故无法通过输入输出进行交互。你需要实现以下函数:

std :: vector < int > solve (std :: vector < int > a)
  • 该函数会被评测机调用恰好一次。
  • 其参数 a 表示 Aob 给出的初始排列。
  • 你需要返回优美的排列中,字典序最小的那个。
  • $n$ 不直接给出,但是你可以通过 a.size() 来得到 $n$。

上述函数可以调用如下函数:

bool query (const std :: vector < int > &vec)
  • vec 表示 Blice 询问的排列。
  • 这个函数会返回一个 bool 变量(true 或者 false),表示这个排列是否是优美的。

为了调用这个函数,你需要在你的函数前加入如下一行代码:(你也可以直接在下发代码基础上进行修改)

bool query (const std :: vector < int > &);

评测工具示例

为方便本机测试,我们下发了一个 sample.cpp,该程序集成了样例 grader。你只需要修改其中的 solve 函数即可。提交时,请务必只提交至 solve 函数的末尾(你可以参考代码中的注释,来了解提交代码时需要提交的范围)。

你可以直接编译运行这份代码,就像往常一样。你应当以如下格式输入测试用例:

  • 第一行,两个空格隔开的整数 $n,m$。
  • 第二行,$n$ 个空格隔开的整数,表示给定的排列 $\{a\}$。
  • 接下来 $m$ 行,每行两个空格隔开的整数,表示 $x_i,y_i$。

然后该程序会与你的 solve 函数进行交互,如果中途出现了错误,那么会产生错误信息。否则,该程序将会以如下格式输出结果:

  • 第一行,$n$ 个空格隔开的整数,表示 solve 返回的结果。

请注意,这份代码仅供测试使用,最终评测系统与此不同。任何试图攻击评测系统的行为都可能导致你的队伍被取消比赛资格。

同时,本题也支持自定义测试。自定义测试的输入输出格式与上述格式相同,且使用的是最终测试时的评测系统

样例输入

3 1
2 0 1
1 0

样例输出

1 0 2

数据规模与约定

对于所有数据,保证 $1\le n\le 400$。

  • Subtask $1$($10\%$):保证 $\forall 0\le a\lt b\lt n$,$\exists 1\le i\le m$,使得 $(x_i,y_i)=(a,b)$,或 $(x_i,y_i)=(b,a)$;
  • Subtask $2$($15\%$):保证 $n\le 8$;
  • Subtask $3$($10\%$):保证 $m=1$;
  • Subtask $4$($15\%$):保证 $\forall 0\le a\lt n$,至多只有一个 $i\in [1,m]$,使得 $x_i=a$ 或 $y_i=a$;
  • Subtask $5$($10\%$):保证 $n\le 100$ 且 $\forall 1\le i\lt n,a_{i-1}\gt a_i$;
  • Subtask $6$($15\%$):保证 $n\le 100$;
  • Subtask $7$($10\%$):保证 $\forall 1\le i\lt n,a_{i-1}\gt a_i$;
  • Subtask $8$($15\%$):无特殊约定。

注意:本题的时间限制以及空间限制均对选手代码与交互器所需时间、空间相加计算。我们保证,对于任意合法的输入,最终评测时使用的交互器运行时间不超过 $700\mathtt{ms}$,峰值内存占用不超过 $256\mathtt{MB}$。这意味着选手程序可以使用至少 $800\mathtt{ms}$ 的时间,以及 $256\mathtt{MB}$ 的空间。


$by\ \text{diamond_duke}$

题解