分数: 1300 点
问题陈述
这是一项交互式任务。
AtCoDeer 鹿遇到了 N 人。为了方便起见,对人进行了编号 0 通过 N-1。 其中, A 是 诚实 以及剩余的 B(=N-A) 是 不友善。 所有这些 N 人们知道谁是诚实的,谁是不仁慈的,但AtCoDeer只知道有 A 诚实和 B 不友善的人。 他试图通过向这些人提出问题来识别所有诚实的人 N 人。 对于一个问题,AtCoDeer 选择 a 和 b (0≤a,b≤N-1),并询问人 a 以下问题:“人是 b 诚实吗?”
诚实的人总是会正确回答“是”或“否”。 然而,不友善的人会选择“是”或“否”来回答 任意。 也就是说,不友善的人使用的算法可能不是简单的算法,例如总是撒谎或随机给出五五十个答案。
AtCoDeer最多可以询问 2N 问题。他会一一提出问题,并且在决定下一个要问的问题时可以使用对前一个问题的回答。
识别所有诚实的人。 如果这是不可能的(更正式地说,如果对于任何询问策略 2N 问题,存在一种让不友善的人回答问题的策略,以便有两组或更多可能的诚实人),报告该事实。
约束
- 1≤A,B≤2000
输入和输出
首先, A 和 B 由标准输入以以下格式给出:
A B
如果无法识别诚实的人,程序必须立即打印以下输出并终止自身:
Impossible
否则,程序将提出问题。 每个问题必须按以下格式写入标准输出:
? a b
在这里, a 和 b 必须是介于 0 和 N-1 (含)。 问题的答案将从标准输入以以下格式给出:
ans
在这里, ans 是 Y or N.
Y 代表“是”; N 代表“否”。
最后,答案必须按以下格式写入标准输出:
! s_0s_1...s_{N-1}
在这里, s_i 必须是 1 如果人 i 是诚实的,并且 0 如果人 i 很不友善。
判断
- 每次输出后,您必须刷新标准输出。 否则你可能会得到
TLE. - 打印答案后,必须立即终止程序。否则,法官的行为是不确定的。
- 当你的输出无效或不正确时,判断的行为是未定义的(它不一定给出
WA).
样品
在以下示例中, A = 2, B = 1,答案是 101.
| 输入 | 输出 |
|---|---|
| 2 1 | |
| ? 0 1 | |
| N | |
| ? 0 2 | |
| Y | |
| ? 1 0 | |
| Y | |
| ? 2 0 | |
| Y | |
| ? 2 2 | |
| Y | |
| ! 101 |
在以下示例中, A = 1, B = 2,答案是 Impossible.
| 输入 | 输出 |
|---|---|
| 1 2 | |
| Impossible |