AtCoder Regular Contest 070
F
HonestOrUnkind
AtCoder
⌀ 3365
原题
← E→
翻译中…

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$
翻译中…
题目信息
题号
arc070_d
时间限制
2 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。