AT_kupc2020_j Median Query

[problemUrl]: https://atcoder.jp/contests/kupc2020/tasks/kupc2020_j **これはインタラクティブな要素がある問題です。** Alice は $ 1 $ から $ N $ までの整数を並び替えた順列 $ a_1,\ a_2,\ \ldots,\ a_N $ を隠し持っています。隠し事が嫌いな Bob はなんとかしてこの順列を特定したいです。できるだけこの順列を隠したい Alice は順列のサイズ $ N $ と以下の $ 2 $ つのタイプの質問の答えのみを教えてくれます。 - タイプ $ 1 $: $ 3 $ つの異なる整数 $ i,j,k(1\ \leq\ i,j,k\ \leq\ N) $ を選び、Alice に聞きます。すると、Alice は $ a_i,a_j,a_k $ の $ 3 $ つの整数の中央値を答えます。 - タイプ $ 2 $: $ 2 $ つの異なる整数 $ i,j(1\ \leq\ i,j\ \leq\ N) $ を選び、Alice に聞きます。すると、Alice は $ a_i,\ a_j $ の小さい方の添え字を答えます。つまり、$ a_i\ $ N $ タイプ $ 1 $ の質問をするときは次の形式に従って出力すること。 > ? $ 1 $ $ i $ $ j $ $ k $ $ i,j,k $ は $ 1 $ から $ N $ までの相異なる整数でなければならない。末尾には改行を出力すること。 タイプ $ 1 $ の質問の答えは以下の形式で与えられる。 > $ m $ $ m $ は $ 1 $ から $ N $ までの整数である。これは $ a_i,a_j,a_k $ の $ 3 $ つの整数の中央値である。 タイプ $ 2 $ の質問をするときは次の形式に従って出力すること。 > ? $ 2 $ $ i $ $ j $ $ i,j $ は $ 1 $ から $ N $ までの相異なる整数でなければならない。末尾には改行を出力すること。 タイプ $ 2 $ の質問の答えは以下の形式で与えられる。 > $ k $ $ k $ は $ i $ または $ j $ である。$ a_i\ ! $ a_1 $ $ a_2 $ $ a_3 $ $ \cdots $ $ a_N $ 順列を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。 また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。 各出力の後には、出力をフラッシュする必要があることに注意せよ。例えば、タイプ $ 1 $ の質問をする際、 C では ``` printf("? 1 %d %d %d\n", i, j, k); fflush(stdout); ``` C++ では ``` cout

N/A

N/A

### 制約 - $ 4\ \leq\ N\ \leq\ 6\ \times\ 10^4 $ ### 部分点 - タイプ $ 1 $ の質問の上限は **$ 3N $** 回、タイプ $ 2 $ の質問の上限は **$ 3 $** 回である。この上限を超えて質問をした場合は *Query Limit Exceeded* となる。 - 質問回数が上限を超えず、かつ正しい順列を出力したとき、$ 20 $ 点が得られる。 - タイプ $ 1 $ の質問が **$ 2N $** 回以内、かつタイプ $ 2 $ の質問が **$ 2 $** 回以内であり、さらに正しい順列を出力したとき、満点が得られる。 ### 入出力例 順列が "$ 3,5,4,1,2 $" である場合に、以下のような入出力が考えられる。 解答プログラムの出力 解答プログラムへの入力 説明 $ 5 $ 順列のサイズ $ 5 $ が入力として与えられる ? $ 1 $ $ 1 $ $ 2 $ $ 3 $ タイプ $ 1 $ の質問をする、$ a_1,\ a_2,\ a_3 $ の中央値を聞いている $ 4 $ $ a_1,\ a_2,\ a_3 $ の中央値は $ 4 $ である ? $ 2 $ $ 2 $ $ 4 $ タイプ $ 2 $ の質問をする、$ a_2 $ と $ a_4 $ ではどちらが小さいか聞いている $ 4 $ $ a_2\ >\ a_4 $ であるので、$ 4 $ が与えられる ? $ 1 $ $ 1 $ $ 5 $ $ 4 $ タイプ $ 1 $ の質問をする、$ a_1,\ a_5,\ a_4 $ の中央値を聞いている $ 2 $ $ a_1,\ a_5,\ a_4 $ の中央値は $ 2 $ である ! $ 3 $ $ 5 $ $ 4 $ $ 1 $ $ 2 $ 順列が "$ 3,5,4,1,2 $" であると回答しているこれは入出力の一つの例であり、意味のある入出力をしているとは限らない。