QOJ.ac

QOJ

Time Limit: 1.0 s Memory Limit: 256 MB Total points: 100 Interactive

#16101. Among Us

統計

在飞船 Skeld 号上,你作为飞船指挥官,与 $N$ 名船员在一起。从地球到 Polus 的航行本应是平静的……直到发生了意外。一系列奇怪的事件接连发生:氧气不足、反应堆几乎熔毁、灯光闪烁、舱门锁死。怀疑在蔓延——我们之中可能混入了冒名顶替者。

危机时刻,船员们团结一致,但紧张气氛挥之不去。现在,每名船员都暗中怀疑恰好一名船员是冒名顶替者。值得注意的是,没有船员被超过一人怀疑。形式化地说,存在一个长度为 $N$ 的排列 $P$,其中 $P[i]$ 是第 $i$ 名船员所怀疑的对象。

作为指挥官,你从指挥室观察着这一切混乱,但你实际上并不关心找出冒名顶替者。相反,你唯一的目标是确定隐藏的排列 $P$。

为了实现这一目标,你可以召开紧急会议。在每次会议中,你可以选择船员发言的顺序。

当一名船员发言时,他们会指控他们所怀疑的船员。如果发言者尚未被标记为“sus”(嫌疑人),则他们的指控有效,被指控的船员变为“sus”。然而,如果发言者已经是“sus”,则他们的指控会被忽略。

不幸的是,作为指挥官,你本人无法参加会议。相反,在每次会议结束后,飞船日志会以二进制数组的形式报告所有船员的“sus”状态,其中 1 表示“sus”,0 表示“not sus”。

由于时间有限,你最多可以召开 400 次紧急会议。你的任务是在此限制内确定隐藏的排列 $P$。

交互

你的程序首先读取一个整数 $N$ ($2 \le N \le 100$),即船员的人数。

然后,你可以重复执行查询(召开紧急会议)。要进行查询,请按以下格式打印一行:

  • ? q1 q2 ... qN

这里,$(q_1, q_2, \dots, q_N)$ 是会议中船员发言的顺序。该序列必须是长度为 $N$ 的排列。

打印查询后,刷新输出并读取包含 $N$ 个整数的一行:

  • s1 s2 ... sN

这里,$s_i$ 表示会议结束后第 $i$ 名船员的状态:

  • $s_i = 0$ —— 第 $i$ 名船员不是“sus”。
  • $s_i = 1$ —— 第 $i$ 名船员是“sus”。

每次紧急会议都是独立的;所有船员开始时均为“not sus”。

当你确定了隐藏的排列 $P$ 后,请按以下格式打印:

  • ! p1 p2 ... pN

打印答案不计入查询次数。打印最终答案后,你的程序应立即终止。否则可能会导致未定义的判决。

你最多可以执行 400 次查询。如果你的程序执行了超过 400 次查询或输出格式错误,你可能会收到 Wrong Answer 判决。

交互器是非自适应的,这意味着隐藏的排列不依赖于你所做的查询。

在打印查询或答案后,请务必输出换行符并刷新输出。否则,你可能会收到 Idleness Limit Exceeded 判决。为此,请使用:

  • C/C++ 中使用 fflush(stdout)cout.flush()
  • Java 和 Kotlin 中使用 System.out.flush()
  • Python 中使用 sys.stdout.flush()

样例

输入 1

6
1 0 1 1 1 0
0 0 1 1 1 1
1 1 1 0 0 1
0 1 1 1 0 1

输出 1

? 1 2 3 4 5 6
? 2 4 3 1 5 6
? 6 5 4 3 2 1
? 3 5 4 2 1 6
! 4 5 3 6 2 1

说明

对于第一次紧急会议,排列 $P$ 为 $[4, 5, 3, 6, 2, 1]$,指控过程如下:

  • 船员 1 指控船员 4。船员 4 变为“sus”。
  • 船员 2 指控船员 5。船员 5 变为“sus”。
  • 船员 3 指控船员 3。船员 3 变为“sus”。
  • 船员 4 指控船员 6,但他们已经是“sus”,因此被忽略。
  • 船员 5 指控船员 2,但他们已经是“sus”,因此被忽略。
  • 船员 6 指控船员 1。船员 1 变为“sus”。
  • 飞船报告船员的状态为 1 0 1 1 1 0。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.