← 返回题目列表

AtCoder · utpc2024_h

H. 隐藏序列旋转

中文机器翻译题面 查看原题

配点 : 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
0 1
1 1
3 1
A(0, 1) = (1), A(1, 1) = (2), A(3, 1) = (1) 进行查询。
2
0
2
0 番目、2 第几个数列是字典序最小的。
? 2
0 3
3 3
A(0, 3) = (1, 2, 3), A(3, 3) = (1, 2, 4) 进行查询。
1
0
0 第几个数列是字典序最小的。
! 1
0
A(s, N) 变为字典序最小 s 是 您也可以写 0 的唯一,因此将其作为答案输出。