AT_utpc2024_h Hidden Sequence Rotation

この問題は**インタラクティブな問題**（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。 整数 $ 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 $ を特定してください。 ### Input & Output Format この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。 最初に、 $ 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 $ 未満の相異なる整数である必要があります。

N/A

N/A

### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が 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 $ のみなので、それを答えとして出力します。 ### Constraints - 入力は全て整数 - $ 1 \leq N \leq 10^{5} $