#arc070d. [arc070_d]HonestOrUnkind

[arc070_d]HonestOrUnkind

现在有 nn 个人,编号从 0n10\sim n-1。这些人中有 aa 个人是诚实的,剩下的 bb 个人是不友好的。这 nn 个人都知道各自的身份,但是你只知道有 aa 个诚实的人和 bb 个不友好的人,你现在试图通过询问来得知他们的身份。

你可以进行询问,询问格式类似于 ? x y,表示向 xx 询问 yy 是否是诚实的。返回答案按照如下规则:

  • 如果 xx 是诚实的人,那么他会按照事实返回答案,也就是说如果 yy 是诚实的,返回答案就为 Y\rm Y,否则返回 N\rm N
  • 如果xx是不友好的人,那么他会任意选择 Y\rm YN\rm N 来回答。也就是说 xx 是可以按照某种策略来回答你的问题的。

现在请你在 2n2n 次询问以内确定 nn 个人的身份,如果不可能,请输出 Impossible,否则请按照 ! S0S1S2...Sn-1 的格式输出(其中 0,1,2,,n10,1,2,\ldots,n-1 都为下标,SiS_i 表示 ii 的身份,如果第 ii 个人是诚实的,请输出 11,否则输出 00,身份之间没有空格)。

如下是一个成功的询问的示例:

void query(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",s);}

上面这个交互函数中的 ss 为字符串变量,用来读入返回的答案。