#arc070d. [arc070_d]HonestOrUnkind

[arc070_d]HonestOrUnkind

题目描述

这是一个交互式的任务。

AtCoDeer鹿与NN个人相遇了。为方便起见,这些人被编号为00N1N-1。其中,有AA个人是_诚实的_,剩下的B(=NA)B(=N-A)个人是_不善良的_。所有这NN个人都知道谁是诚实的,谁是不善良的,但是AtCoDeer只知道有AA个诚实和BB个不善良的人。他试图通过向这NN个人提问来确定所有诚实的人。对于一个问题,AtCoDeer选择aabb (0a,bN1)(0≤a,b≤N-1),并向第aa个人提问以下问题:“第bb个人是诚实的吗?”

一个诚实的人总是正确回答“是”或“否”。然而,一个不善良的人会任意地选择“是”或“否”回答。也就是说,不善良的人使用的算法可能不是简单的算法,如总是撒谎或随机选择二分之一的概率回答。

AtCoDeer最多可以提问2N2N个问题。他会逐个提问,并在决定下一个问题时可使用前面问题的回答。

确定所有诚实的人。如果不可能确定(更正式地说,如果对于提问2N2N个问题的任何策略,都存在一种未善良人回答问题的策略,以便获得两个或更多可能的诚实人集合),报告这个事实。

约束条件

  • 1A,B20001≤A,B≤2000

输入和输出

首先,从标准输入按照以下格式给出AABB

AA BB

如果不能确定诚实的人,则程序必须立即打印以下输出并终止自己:

Impossible

否则,程序应该提问。每个问题必须按照以下格式写入标准输出:

? aa bb

这里,aabb必须是介于00N1N-1(包括边界)之间的整数。对问题的回答将从标准输入按照以下格式给出:

ansans

这里,ansans可以是YNY表示“是”;N表示“否”。

最后,答案必须按照以下格式写入标准输出:

! s0s1...sN1s_0s_1...s_{N-1}

这里,如果第ii个人是诚实的,则sis_i必须为1,如果第ii个人是不善良的,则sis_i必须为0

判定

  • **在每次输出之后,必须清空标准输出。**否则可能会导致TLE
  • 在打印答案后,程序必须立即终止。否则,判定器的行为是未定义的。
  • 当你的输出无效或错误时,判定器的行为是未定义的(不一定给出WA)。

示例

以下示例中,A=2A = 2B=1B = 1,答案为101

输入

输出

22 11

?? 00 11

NN

?? 00 22

YY

?? 11 00

YY

?? 22 00

YY

?? 22 22

YY

!! 101101

以下示例中,A=1A = 1B=2B = 2,答案为Impossible

输入

输出

11 22

ImpossibleImpossible