No.3811 Mid Filter
問題文
これはインタラクティブな問題です。
$(1,2,\ldots,N)$ の順列 $A=(A_1,A_2,\ldots,A_N)$ があります。$N$ と $K$ が与えられますが、$A$ は与えられません。
あなたは、次の質問を $N$ 回まで行うことができます。
- $1$ 以上 $N$ 以下の相異なる整数 $s_1,s_2,\ldots,s_{2K}$ を選ぶ。$(A_{s_1},A_{s_2},\ldots,A_{s_{2K}})$ を昇順に並べた列を $B$ とするとき、$A_r=B_K$ を満たす添字 $r$ を聞く。
$A_j\leq K$ を満たす添字 $j$ をすべて求めてください。
順列 $A$ は対話の開始前に固定され、質問に応じて変更されることはありません。
制約
- $1\leq K\leq1000$
- $3K\leq N\leq3000$
- $A$ は $(1,2,\ldots,N)$ の順列
- 入力はすべて整数
入力
最初に、以下の形式で標準入力から $N$ と $K$ が与えられます。
$N$ $K$
質問を行うと、選んだ添字の中で $A$ の値が $K$ 番目に小さい添字 $r$ が、標準入力から $1$ 行で与えられます。応答は値 $A_r$ ではなく添字 $r$ です。
$r$
不正な質問を行った場合や質問回数が $N$ 回を超えた場合は、応答として -1 が与えられます。-1 を受け取った場合は、直ちにプログラムを終了してください。
出力
質問を行うときは、以下の形式で標準出力に $1$ 行出力してください。
? $s_1$ $s_2$ $\ldots$ $s_{2K}$
各 $s_i$ は $1$ 以上 $N$ 以下の整数であり、互いに異なる必要があります。
答えが分かったら、$A_j\leq K$ を満たす $K$ 個の添字を、以下の形式で標準出力に $1$ 行出力してプログラムを終了してください。添字の順序は任意です。
! $j_1$ $j_2$ $\ldots$ $j_K$
最終回答は質問回数に含まれません。
質問または最終回答を出力するたびに、改行し、標準出力を flush してください。 flush しない場合は、実行時間制限超過になる可能性があります。
サンプル
以下の表は対話の例です。各行では、左欄または右欄のいずれか一方の出力が行われます。表中の — は、その行で出力しないことを表します。
サンプル1
$N=6$ かつ $K=2$ で、隠された順列が $A=(4,1,6,2,5,3)$ の場合の対話例です。
| ジャッジの出力 | 解答プログラムの出力 |
|---|---|
6 2 | — |
| — | ? 2 3 4 5 |
4 | — |
| — | ? 1 3 4 5 |
1 | — |
| — | ? 1 2 4 5 |
4 | — |
| — | ? 1 2 3 5 |
1 | — |
| — | ? 1 2 3 4 |
4 | — |
| — | ? 2 4 6 1 |
4 | — |
| — | ! 2 4 |
最初の質問で選んだ値は $(1,6,2,5)$ です。昇順に並べると $(1,2,5,6)$ となり、$2$ 番目の値 $2$ を持つ添字 $4$ が返されます。
$A_2=1$ かつ $A_4=2$ なので、最終回答 ! 2 4 は正解です。
サンプル2
$N=3$ かつ $K=1$ で、隠された順列が $A=(3,1,2)$ の場合の対話例です。
| ジャッジの出力 | 解答プログラムの出力 |
|---|---|
3 1 | — |
| — | ? 2 3 |
2 | — |
| — | ? 1 3 |
3 | — |
| — | ? 1 2 |
2 | — |
| — | ! 2 |
$A_2=1$ なので、最終回答 ! 2 は正解です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
sepa38