AT_kupc2020_l Inside Story of Median Query

[problemUrl]: https://atcoder.jp/contests/kupc2020/tasks/kupc2020_l **これはインタラクティブな要素がある問題です。** Alice は $ 1 $ から $ N $ までの整数を並び替えた順列を隠し持っています。Alice には Bob という友達がいます。Bob は隠し事が嫌いなので、この順列を特定しようと質問してくることが予想されます。その質問をなるべくかわして特定されないようにするため、Alice は Oscar と模擬訓練を行って練習することにしました。 模擬訓練は質問フェーズと解答フェーズからなります。質問フェーズでは、Alice は順列に関するいくつかの質問に答えなければなりません。その後の解答フェーズでは、質問の解答に矛盾しない順列 $ a_1,\ a_2,\ \ldots,\ a_N $ を $ 2 $ つ構成しなければなりません。 質問フェーズでは、いくつかの質問が与えられるので順番に答えてください。はじめ、Oscar のスタミナ $ S $ は $ 2N $ であり、質問するたびにスタミナを消費します。質問には **$ 3 $** 種類あり、以下の形式で与えられます。 - タイプ $ 1 $: $ 3 $ つの相異なる整数 $ i,j,k $ が与えられる。$ 3 $ つの整数 $ a_i,a_j,a_k $ の中央値となるべき整数 $ m $ を回答せよ。$ m $ は $ 1 $ 以上 $ N $ 以下でなければならない。この質問をすると Oscar のスタミナ $ S $ は $ 2 $ 減少する。 - タイプ $ 2 $: $ 2 $ つの異なる整数 $ i,j $ が与えられる。$ a_i\ \ a_j $ となるべきであれば $ j $ を回答せよ。この質問をすると Oscar のスタミナ $ S $ は $ 2 $ 減少する。 - タイプ $ 3 $: $ 2 $ つの異なる整数 $ i,j $ が与えられる。$ a_i,a_j $ の最小値となるべき整数 $ x $ を回答せよ。$ x $ は $ 1 $ 以上 $ N $ 以下でなければならない。この質問をすると Oscar のスタミナ $ S $ は $ 1 $ 減少する。 質問には必ず答える必要があります。また、Oscar は疲れてしまうので、 **質問した後に Oscar のスタミナ $ S $ が $ 2 $ 以下になることはありません。** 質問フェーズが終了すると、解答フェーズとなります。 解答フェーズでは、$ 2 $ つの $ 1 $ から $ N $ までの整数を並び替えた順列 $ a_1,\ a_2,\ \ldots,\ a_N $ と $ b_1,\ b_2,\ \ldots,\ b_N $ を Oscar に伝えます。この $ 2 $ つの順列は、それぞれの質問フェーズでのすべての回答に矛盾しない順列であり、$ a_i\ \neq\ b_i $ となる $ i $ の個数が $ \left\lceil\ \frac{S}{2}\ \right\rceil $ 以上であれば、Oscar は混乱します。ここでの $ S $ は、Oscar がすべての質問を終えた後のスタミナです。Oscar が混乱するような $ 2 $ つの順列を伝えることができれば Alice の勝ちです。このような $ 2 $ つの順列を構成できることが証明できます。 Alice にとって Oscar が混乱するような $ 2 $ つの順列を探し出すのは非常に難しく、意気消沈してしまいました。どのような質問が来ても Oscar が混乱するような $ 2 $ つの順列を出力するプログラムを作成し、Alice を元気づけてください。 ### Input & Output Format 最初に順列のサイズ $ N $ が $ 1 $ 行で与えられる。 > $ N $ その後、タイプ $ 1,2,3 $ の質問、もしくは解答フェーズの開始を表す記号が入力として与えられる。 タイプ $ 1 $ の質問は以下の形式で与えられる。 > ? $ 1 $ $ i $ $ j $ $ k $ $ i,j,k $ は $ 1 $ から $ N $ までの相異なる整数である。 次に、質問への回答を以下の形式で出力すること。 > $ m $ $ m $ は $ 1 $ から $ N $ までの整数でなければならない。さらに、これは $ a_i,a_j,a_k $ の $ 3 $ つの整数の中央値であり、$ b_i,b_j,b_k $ の $ 3 $ つの整数の中央値である必要がある。末尾には改行を出力すること。 タイプ $ 2 $ の質問は以下の形式で与えられる。 > ? $ 2 $ $ i $ $ j $ $ i,j $ は $ 1 $ から $ N $ までの相異なる整数である。 次に、質問への回答を以下の形式で出力すること。 > $ p $ $ p $ は $ i $ または $ j $ の整数でなければならない。さらに、$ p=i $ であれば $ a_i\ \ b_j $ である必要がある。末尾には改行を出力すること。 タイプ $ 3 $ の質問は以下の形式で与えられる。 > ? $ 3 $ $ i $ $ j $ $ i,j $ は $ 1 $ から $ N $ までの相異なる整数である。 次に、質問への回答を以下の形式で出力すること。 > $ x $ $ x $ は $ x=\min(a_i,a_j)=\min(b_i,b_j) $ を満たす必要がある。末尾には改行を出力すること。 解答フェーズに移るとき、以下の形式で解答フェーズの開始を表す記号が与えられる。 ``` ! ``` この後、 $ 2 $ つの順列を以下の形式で出力すること。 > $ a_1 $ $ a_2 $ $ \cdots $ $ a_N $ $ b_1 $ $ b_2 $ $ \cdots $ $ b_N $ Bob の残りのスタミナが $ S $ の時、順列 $ a_i\ \neq\ b_i $ となる $ i $ の個数が $ \left\lceil\ \frac{S}{2}\ \right\rceil $ 以上である必要がある。末尾には改行を出力すること。 $ 2 $ つの順列を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。 また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。 各出力の後には、出力をフラッシュする必要があることに注意せよ。例えば、タイプ $ 1 $ の質問に対して答える際、 C では ``` printf("%d\n", m); fflush(stdout); ``` C++ では ``` cout

N/A

N/A

### 制約 - $ 4\ \leq\ N\ \leq\ 5\ \times\ 10^4 $ - $ N $ は整数 ### 入出力例 以下のような入出力が考えられる。 解答プログラムの出力 解答プログラムへの入力 説明 $ 5 $ 順列のサイズ $ 5 $ が入力として与えられる。Bob のスタミナは $ 10 $ である。 ? $ 1 $ $ 1 $ $ 2 $ $ 3 $ タイプ $ 1 $ の質問がされる。Bob のスタミナは $ 8 $ となる。 $ 4 $ $ a_1,\ a_2,\ a_3 $ の中央値が $ 4 $ である順列がこの質問に合致する。 ? $ 2 $ $ 2 $ $ 4 $ タイプ $ 2 $ の質問がされる。Bob のスタミナは $ 6 $ となる。 $ 4 $ $ a_2\ >\ a_4 $ となる順列がこの質問に合致する。 ? $ 3 $ $ 4 $ $ 5 $ タイプ $ 3 $ の質問がされる。Bob のスタミナは $ 5 $ となる。 $ 1 $ $ \min(a_4,\ a_5)=1 $ となる順列がこの質問に合致する。 ! 解答フェーズに入る。 $ 3 $ $ 5 $ $ 4 $ $ 1 $ $ 2 $ $ 5 $ $ 4 $ $ 3 $ $ 2 $ $ 1 $ 2 つの順列 "$ 3,5,4,1,2 $" と "$ 5,4,3,2,1 $" を出力している。これは共に質問フェーズでのすべての回答に矛盾せず、$ \lceil\ 5/2\ \rceil\ =\ 3 $ 個以上の要素が異なるので正解となる。これは入出力の一つの例であり、意味のある入出力をしているとは限らない。