配点 : 100 点
問題文
这个问题是互动问题(这是您创建的程序和判断程序通过标准输入和输出交互的问题)。 有
整数 N 会被赋予。裁判员隐藏着 1 以上 10^5 长度由小于或等于的整数组成 N 序列 使用 A = (A_{0}, \dots, A_{N-1}) 。请注意,包括以下内容在内,下标从 0 开始。对于
整数 s = 0, \dots, N-1 和 l = 1, \dots, N ,数列 A(s, l) 如下。
- 长度 小于或等于 l 的数列,其第i=0,\dots,l-1 个元素分别为 A_{(s+i) \bmod N} 的那些
,你可以向裁判员提出如下格式的问题 20 次。 交换
- 。你要输出的是由整数对组成的序列 ((s_0,l_0),\dots,(s_{k-1},l_{k-1})) ,满足以下约束条件。对于此,裁判员会回复
- 1 \le k \le N
- 0 \le s_i < N
- 1 \le l_i \le N
- \sum_{i = 0}^{k - 1} l_i \leq N
- ,以使 i = 0, \dots, k - 1 中 找出满足 A(s_i, l_i) 在字典序上最小化的 i 全部返回。也就是说,当A_{\mathrm{tmpmin}} = \min_{0 \le i < k} A(s_i, l_i) 时,返回集合 \lbrace i_0, \dots, i_{k'-1} \rbrace \coloneqq \lbrace i \mid 0 \le i < k, \, A(s_i,l_i) = A_{\mathrm{tmpmin}} \rbrace 。通过上述问题,
全部确定。也就是说,s = 0, \dots, N - 1 中 找出满足 A(s, N) 在字典序上最小化的 s 。A_{\mathrm{min}} = \min_{0 \leq s < N} A(s,N) 时,返回集合 \lbrace s_0, \dots, s_{n-1} \rbrace \coloneqq \lbrace s \mid 0 \le s < N, \, A(s, N) = A_{\mathrm{min}} \rbrace 。
制約
- 所有输入均为整数
- 1 \leq N \leq 10^{5}
入出力
这个问题是一个交互问题(你的程序和判断程序通过标准输入和输出交互的问题)。
首先,N 。
N
之后,您可以提出问题。请将问题以以下格式输出到标准输出。
? k
s_0 l_0
s_1 l_1
\vdots
s_{k-1} l_{k-1}
此处,输出必须满足题目中所述问题的条件。
如果问题是合法的,那么该问题的答案将以以下格式从标准输入给出。
k'
i_0
i_1
\vdots
i_{k'-1}
此处,输入必须满足 0 \le i_0 < \dots < i_{k'-1} < k 的条件。
如果问题格式错误,或者提问次数超过规定次数等原因被判定为非法问题,则在问题的答案中 -1 。
对于
-1
-1 被输入时,请立即结束程序。
如果知道答案,请以以下格式输出到标准输出。
! n
s_0
s_1
\vdots
s_{n-1}
在这里,s_i 是 您也可以写 0 以上 N 必须是小于 未同的整数。
注意点
- 每次打印输出时,在末尾添加一个换行符并刷新标准输出。如果不这样做,判断结果将是 TLE 。
- 如果对话过程中输出错误或程序中途终止,则判断结果不确定。
- 当输出答案(或收到
-1时)请立即正常结束程序。否则,评测结果不确定。 - 特别要小心,因为额外的换行符也被视为无效的格式化输出。
- 判题器不是自适应的。也就是说,数列 A 在对话开始时固定,并且在对话过程中不会更改。
入出力例
以下是 N = 6, A=(1, 2, 3, 1, 2, 4) 的输入/输出示例。
| 入力 | 出力 | 説明 |
|---|---|---|
6 |
N 。 对于 | |
? 3 |
A(0, 1) = (1), A(1, 1) = (2), A(3, 1) = (1) 进行查询。 | |
2 |
0 番目、2 第几个数列是字典序最小的。 | |
? 2 |
A(0, 3) = (1, 2, 3), A(3, 3) = (1, 2, 4) 进行查询。 | |
1 |
0 第几个数列是字典序最小的。 | |
! 1 |
A(s, N) 变为字典序最小 s 是 您也可以写 0 的唯一,因此将其作为答案输出。 |