310587: CF1855F. Michael and Hotel
Description
Michael and Brian are stuck in a hotel with $n$ rooms, numbered from $1$ to $n$, and need to find each other. But this hotel's doors are all locked and the only way of getting around is by using the teleporters in each room. Room $i$ has a teleporter that will take you to room $a_i$ (it might be that $a_i = i$). But they don't know the values of $a_1,a_2, \dots, a_n$.
Instead, they can call up the front desk to ask queries. In one query, they give a room $u$, a positive integer $k$, and a set of rooms $S$. The hotel concierge answers whether a person starting in room $u$, and using the teleporters $k$ times, ends up in a room in $S$.
Brian is in room $1$. Michael wants to know the set $A$ of rooms so that if he starts in one of those rooms they can use the teleporters to meet up. He can ask at most $2000$ queries.
The values $a_1, a_2, \dots, a_n$ are fixed before the start of the interaction and do not depend on your queries. In other words, the interactor is not adaptive.
InputThe input contains a single integer $n$ ($2 \leq n \leq 500$).
InteractionTo ask a query, print a line in the format "? u k |S| S_1 S_2 ... S_|S|" with $1 \leq u, S_1, \ldots, S_{|S|} \leq n$, all the $S_i$ distinct, and $1 \leq k \leq 10^9$.
As a response to the query you will get "1" if the answer is yes, and "0" if the answer is no.
To output an answer, you should print "! |A| A_1 A_2 ... A_|A|" with $1 \leq A_1, \ldots, A_{|A|} \leq n$ all distinct. Printing the answer doesn't count as a query.
See the interaction example for more clarity.
If you ask too many queries or you ask a malformed query, you will get Wrong answer.
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hack format
For the hacks use the following format.
The first line should contain $n$ — the number of rooms.
The second line should contains $n$ integers $a_1, a_2, \dots, a_n$ — the teleporter in room $i$ leads to room $a_i$.
ExampleInput5 0 1Output
? 3 5 2 2 3 ? 2 5 2 2 3 ! 3 1 3 4Note
In the sample test, there are $n=5$ rooms and the (hidden) array describing the behavior of the teleporters is $[1, 2, 1, 3, 2]$.
- The first query asks whether starting from room number $a=3$, and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$. This action results in ending up in the room $1$, so the answer is $0$.
- The second query asks whether starting from room number $a=2$, and using the teleporters $5$ times, one ends up in one of the two rooms $S=\{2, 3\}$. This action results in ending up in the room $2$, so the answer is $1$.
Input
Output
Michael和Brian被困在一个有n个房间的酒店中,房间编号从1到n,他们需要找到彼此。酒店的每扇门都锁上了,唯一的移动方式是通过每个房间中的传送器。房间i有一个传送器,可以将你传送到房间a_i(可能是a_i = i)。但他们不知道a_1, a_2, ..., a_n的值。
他们可以打电话给前台进行查询。在一次查询中,他们给出一个房间u,一个正整数k,和一个房间集合S。酒店礼宾回答一个人从房间u开始,使用传送器k次后,是否最终到达S中的某个房间。
Brian在房间1。Michael想知道如果他从这些房间中的一个开始,他们是否可以使用传送器相遇。他最多可以询问2000次。
a_1, a_2, ..., a_n的值在交互开始前就已经确定,不依赖于你的查询。换句话说,交互器不是自适应的。
输入输出数据格式:
输入包含一个整数n(2 ≤ n ≤ 500)。
进行查询时,请按照格式"? u k |S| S_1 S_2 ... S_|S|"打印一行,其中1 ≤ u, S_1, ..., S_|S| ≤ n,所有S_i都是不同的,1 ≤ k ≤ 10^9。
作为对查询的响应,如果答案是肯定的,你会得到"1",如果答案是否定的,你会得到"0"。
输出答案时,应按照格式"! |A| A_1 A_2 ... A_|A|"打印,其中1 ≤ A_1, ..., A_|A| ≤ n,所有A_i都是不同的。打印答案不计入查询次数。
如果询问过多查询或询问格式错误,将得到"Wrong answer"。
在打印查询后,别忘了输出换行符并刷新输出。否则,你将得到"Idleness limit exceeded"。具体刷新输出的方法取决于使用的编程语言。
对于黑客攻击,请使用以下格式:
第一行包含n — 房间的数量。
第二行包含n个整数a_1, a_2, ..., a_n — 房间i的传送器通向房间a_i。题目大意: Michael和Brian被困在一个有n个房间的酒店中,房间编号从1到n,他们需要找到彼此。酒店的每扇门都锁上了,唯一的移动方式是通过每个房间中的传送器。房间i有一个传送器,可以将你传送到房间a_i(可能是a_i = i)。但他们不知道a_1, a_2, ..., a_n的值。 他们可以打电话给前台进行查询。在一次查询中,他们给出一个房间u,一个正整数k,和一个房间集合S。酒店礼宾回答一个人从房间u开始,使用传送器k次后,是否最终到达S中的某个房间。 Brian在房间1。Michael想知道如果他从这些房间中的一个开始,他们是否可以使用传送器相遇。他最多可以询问2000次。 a_1, a_2, ..., a_n的值在交互开始前就已经确定,不依赖于你的查询。换句话说,交互器不是自适应的。 输入输出数据格式: 输入包含一个整数n(2 ≤ n ≤ 500)。 进行查询时,请按照格式"? u k |S| S_1 S_2 ... S_|S|"打印一行,其中1 ≤ u, S_1, ..., S_|S| ≤ n,所有S_i都是不同的,1 ≤ k ≤ 10^9。 作为对查询的响应,如果答案是肯定的,你会得到"1",如果答案是否定的,你会得到"0"。 输出答案时,应按照格式"! |A| A_1 A_2 ... A_|A|"打印,其中1 ≤ A_1, ..., A_|A| ≤ n,所有A_i都是不同的。打印答案不计入查询次数。 如果询问过多查询或询问格式错误,将得到"Wrong answer"。 在打印查询后,别忘了输出换行符并刷新输出。否则,你将得到"Idleness limit exceeded"。具体刷新输出的方法取决于使用的编程语言。 对于黑客攻击,请使用以下格式: 第一行包含n — 房间的数量。 第二行包含n个整数a_1, a_2, ..., a_n — 房间i的传送器通向房间a_i。