問題一覧 > 通常問題

No.3811 Mid Filter

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : dyktr_06 / テスター : sepa38
お気に入りにしたユーザー ProblemId : 14114 / 自分の提出
問題文最終更新日: 2026-11-20 00:01:26
yukicoder contest 524 (順位表) の他の問題:

問題文

これはインタラクティブな問題です。

$(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もしくは右上の雲マークをクリックしてアカウントを作成してください。