200703: [AtCoder]ARC070 F - HonestOrUnkind

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $1300$ points

Problem Statement

This is an interactive task.

AtCoDeer the deer came across $N$ people. For convenience, the people are numbered $0$ through $N-1$. Among them, $A$ are honest and the remaining $B(=N-A)$ are unkind. All of these $N$ people know who are honest and who are unkind, but AtCoDeer only knows that there are $A$ honest and $B$ unkind people. He is trying to identify all of the honest people by asking questions to these $N$ people. For one question, AtCoDeer selects $a$ and $b$ $(0≤a,b≤N-1)$, and asks person $a$ the following question: "Is person $b$ honest?"

An honest person will always answer correctly by "Yes" or "No". An unkind person, however, will answer by selecting "Yes" or "No" arbitrarily. That is, the algorithm used by an unkind person may not be simple one such as always lying or giving random fifty-fifty answers.

AtCoDeer can ask at most $2N$ questions. He will ask questions one by one, and the responses to the previous questions can be used when deciding the next question to ask.

Identify all of the honest people. If it is impossible (more formally, if, for any strategy of asking $2N$ questions, there exists a strategy for unkind people to answer the questions so that there are two or more possible sets of the honest people), report that fact.

Constraints

  • $1≤A,B≤2000$

Input and Output

First, $A$ and $B$ are given from Standard Input in the following format:

$A$ $B$

If identifying the honest people is impossible, the program must immediately print the following output and terminate itself:

Impossible

Otherwise, the program shall ask questions. Each question must be written to Standard Output in the following format:

? $a$ $b$

Here, $a$ and $b$ must be integers between $0$ and $N-1$ (inclusive). The response to the question will be given from Standard Input in the following format:

$ans$

Here, $ans$ is either Y or N. Y represents "Yes"; N represents "No".

Finally, the answer must be written to Standard Output in the following format:

! $s_0s_1...s_{N-1}$

Here, $s_i$ must be 1 if person $i$ is honest, and 0 if person $i$ is unkind.

Judgement

  • After each output, you must flush Standard Output. Otherwise you may get TLE.
  • After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Samples

In the following sample, $A = 2$, $B = 1$, and the answer is 101.

Input Output
$2$ $1$
$?$ $0$ $1$
$N$
$?$ $0$ $2$
$Y$
$?$ $1$ $0$
$Y$
$?$ $2$ $0$
$Y$
$?$ $2$ $2$
$Y$
$!$ $101$

In the following sample, $A = 1$, $B = 2$, and the answer is Impossible.

Input Output
$1$ $2$
$Impossible$

Input

题意翻译

现在有 $n$ 个人,编号从 $0\sim n-1$。这些人中有 $a$ 个人是诚实的,剩下的 $b$ 个人是不友好的。这 $n$ 个人都知道各自的身份,但是你只知道有 $a$ 个诚实的人和 $b$ 个不友好的人,你现在试图通过询问来得知他们的身份。 你可以进行询问,询问格式类似于 `? x y`,表示向 $x$ 询问 $y$ 是否是诚实的。返回答案按照如下规则: - 如果 $x$ 是诚实的人,那么他会按照事实返回答案,也就是说如果 $y$ 是诚实的,返回答案就为 $\rm Y$,否则返回 $\rm N$。 - 如果$x$是不友好的人,那么他会**任意**选择 $\rm Y$ 和 $\rm N$ 来回答。也就是说 $x$ 是可以按照某种策略来回答你的问题的。 现在请你在 $2n$ 次询问以内确定 $n$ 个人的身份,如果不可能,请输出 `Impossible`,否则请按照 `! S0S1S2...Sn-1` 的格式输出(其中 $0,1,2,\ldots,n-1$ 都为下标,$S_i$ 表示 $i$ 的身份,如果第 $i$ 个人是诚实的,请输出 $1$,否则输出 $0$,身份之间没有空格)。 如下是一个成功的询问的示例: ```cpp void query(int x,int y){printf("? %d %d\n",x,y);fflush(stdout);scanf("%s",s);} ``` 上面这个交互函数中的 $s$ 为字符串变量,用来读入返回的答案。

加入题单

上一题 下一题 算法标签: