実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
これはインタラクティブな要素がある問題です。
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 となるべきであれば i を、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 を元気づけてください。
制約
- 4 \leq N \leq 5 \times 10^4
- N は整数
入出力
最初に順列のサイズ 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 < a_j かつ b_i < b_j、p=j であれば a_i > a_j かつ b_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<<m<<endl;
と出力すればよい。
入出力例
以下のような入出力が考えられる。
解答プログラムの出力 | 解答プログラムへの入力 | 説明 |
---|---|---|
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 個以上の要素が異なるので正解となる。 |
これは入出力の一つの例であり、意味のある入出力をしているとは限らない。