| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 56 | 10 | 7 | 16.667% |
Pak Dengklek is organizing a party at his place. This party is attended by $N + M$ guests, numbered $1$ to $N + M$. The guests numbered $1$ to $N$ are male guests, while the guests numbered $N + 1$ to $N + M$ are female guests.
Each guest gets acquainted with zero or more other guests that have the opposite gender. If the guest $x$ gets acquainted with guest $y$, then guest $y$ also gets acquainted with guest $x$. Since the duration of the party is quite short, usually each guest gets acquainted by exactly one other guest. A guest is said to be unusual if the guest does not get acquainted with other guests or gets acquainted with more than one other guests.
After checking the guest list, Pak Dengklek notices that the number of male guests is not the same as the number of female guests. Therefore, there must be at least one unusual guest. You want to help Pak Dengklek to identify any unusual guest.
You can ask at most $7$ questions to Pak Dengklek. For each question, you can ask a set of guests. Pak Dengklek will answer the set of guests that get acquainted with at least one guest in the set. In other words, if you ask a set of guests $A$, then a guest $y$ will be in the set answered by Pak Dengklek if and only if there is a guest $x$ in the set $A$ and guest $x$ gets acquainted with guest $y$.
In the beginning, the values of $N$ and $M$ will be given from standard input in the following format: $N$ $M$ ($1 ≤ N, M ≤ 50$; $N \ne M$). Then, not more than $7$ times, you can output to standard output in the following format: ? $X$ $A_1$ $A_2$ $\dots$ $A_X$. This means you ask the set of guests $\{A_1, A_2, \dots , A_X\}$ to Pak Dengklek. The values of $A_1, A_2, \dots , A_X$ asked have to satisfy $1 ≤ A[1] < A[2] < \cdots < A[X] ≤ N +M$. The set $B = \{B_1, B_2, \dots , B_Y\}$ (the set answered by Pak Dengklek) will be given from standard input in the following format: $Y$ $B_1$ $B_2$ $\dots$ $B_Y$. The values of $B_1, B_2, \dots , B_Y$ are guaranteed to satisfy $1 ≤ B[1] < B[2] < \cdots < B[Y ] ≤ N + M$. It is also guaranteed that each guest gets acquainted only with guests that have the opposite gender. In the end, your answer has to be outputted to standard output in the following format: ! $Z$. This means you guess that the guest $Z$ is an unusual guest. Your answer will be considered as correct if the guest $Z$ does not get acquainted with other guests or gets acquainted with more than one other guests.
Do not forget to flush output buffers after each write.
fflush(stdout).fflush(stdout) for stdio.h (cstdio) library or cout << flush for iostream library.flush for output stream, for example, System.out.flush().stdout.flush().3 5 7 1 2 3 4 5 6 8 4 4 5 6 8 3 1 2 3 2 1 4
? 8 1 2 3 4 5 6 7 8 ? 3 1 2 3 ? 5 4 5 6 7 8 ? 2 1 4 ! 7
In the following sample, $N = 3$, $M = 5$, and:
Also note that “! $2$” or “! $6$” in the last line is also a correct output.
ICPC > Regionals > Asia Pacific > Indonesia > Jakarta > The 2023 ICPC Asia Jakarta Regional Contest 연습 세션 PC번