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

スイーツフェスティバルの開幕を目前に控え、シェフは店の看板作品である「千层幻彩慕斯」を丹念に仕上げています。このスイーツは、風味の異なる $n$ 個のムースからなり、それぞれ $0,1,\dots,n-1$ の番号が付いています。

しかし、慌ただしい中で、助手がうっかりムースの並び順を取り違えてしまいました。今、それらは左から右へ一列に並んでおり、未知の順列 $p=(p_0,p_1,\dots,p_{n-1})$ をなしています。ここで $p_i$ は、位置 $i$ に置かれたムースの番号を表します。

各ムースの正確な位置を知るために、スイーツ検査装置を使うことができます。検査のたびに、互いに異なる 3 つの位置 $x,y,z$ を選ぶと、装置はこれらのムースの番号の最小値と最大値の和を返します。

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

開幕を告げる鐘がまもなく鳴ります。限られた回数の検査で、すべてのムースの本当の位置を正確に復元できるでしょうか？

長さ $n$ の順列 $p$ があり、その要素はちょうど $0,1,\ldots,n-1$ です。あなたは $p$ の具体的な内容を知りません。

互いに異なる 3 つの添字 $x,y,z$ を選ぶことができ、インタラクション用ライブラリは次の値を返します。

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

あなたの課題は、順列全体を復元することです。クエリ回数の上限と、クエリ回数に応じた得点の計算方法は以下に示します。

実装の詳細

main 関数を実装する必要はなく、実装してはいけません。提出するソースファイルには、次を含めてください。

#include "mousse.h"

以下の 2 つの関数を実装してください。

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$ は小課題の番号であり、$c=0$ は入出力例を表します。各テストケースには、ちょうど 1 組のデータが含まれます。インタラクション用ライブラリは、そのテストケースについて init(c) を 1 回呼び出し、その後 mousse(c,n) を 1 回呼び出します。
• mousse は長さ $n$ の配列を返してください。その第 $i$ 要素は $p_i$ であり、添字は $0$ から始まります。

以下の関数を呼び出すことで、1 回のクエリを行うことができます。

int query(int x, int y, int z);

$0\le x,y,z < n$ を満たし、$x,y,z$ は互いに異ならなければなりません。この関数は $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$ を返します。

プログラムのテスト方法

添付ファイルには mousse.h、ローカルのインタラクション用ライブラリ grader.cpp、サンプルプログラム template_mousse.cpp が含まれています。自分のプログラムを mousse.cpp として保存すると、この問題のディレクトリで次のコマンドを実行できます。

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

ローカルのインタラクション用ライブラリは、標準入力から隠された順列を読み込みます。競技者のプログラムがこれらのデータを直接読み込んではいけません。入力形式は以下の通りです。

• 1 行目に 2 つの整数 $c,n$ が与えられます。
• 2 行目に $p_0,p_1,\ldots,p_{n-1}$ が与えられます。

解答が正しい場合、ライブラリは Correct! と Max queries used: Q を出力します。ここで $Q$ は、そのテストケースでのクエリ回数です。解答が誤っている場合、Wrong answer. を出力します。不正なクエリを渡した場合やクエリ回数の上限を超えた場合、プログラムは標準エラー出力にエラーメッセージを出力して終了します。-v オプションを追加すると、そのテストケースでのクエリ回数を確認できます。

入出力例

入力 1

0 10
0 2 9 1 5 8 3 7 6 4

出力 1

Correct!
Max queries used: 15

注記

例えば query(0,1,2) を呼び出すと、対応する 3 つの値は $0,2,9$ であり、$0+9=9$ が返されます。参照プログラムは、このデータに対して $15$ 回のクエリを使用します。別の戦略を用いた場合、この回数は異なることがあります。

制約

すべてのテストデータについて、$n\in\{10,100,10^5\}$ であり、$p$ は $0\sim n-1$ の順列です。各テストケースには、ちょうど 1 組のデータが含まれます。

入出力例では $c=0$、$n=10$ であり、クエリ回数の上限は $1000$ です。

小課題

以下に注意してください。

• インタラクション用ライブラリは適応的ではありません。各テストケースの順列は、競技者のプログラムを呼び出す前に確定しており、クエリによって変化しません。
• 競技者は、標準入力を読み込むなどの不正な方法によって、隠された順列を取得してはいけません。本番の採点に用いるインタラクション用ライブラリは、ローカルのライブラリと実装が異なる可能性があります。

あるテストケースにおいて、mousse が誤った解答を返した場合、query の引数が不正な場合、またはクエリ回数がその小課題の $Q_{\max}$ を超えた場合、そのテストケースの得点倍率は $0$ になります。

小課題 $1,2$ では、すべてのテストケースで正解した場合に限り、その小課題の満点を獲得できます。

小課題 $3,4$ では、いずれかのテストケースの得点倍率が $0$ の場合、その小課題の得点は $0$ 点になります。そうでなければ、その小課題のすべてのテストケースにおけるクエリ回数の最大値を $Q$ とします。得点倍率 $f(Q)$ は以下の表によって定まります。

$Q\le 99970$ の場合、$f(Q)=100\%$ です。$Q$ が表の隣り合う 2 行 $(Q_i,f_i)$ と $(Q_{i+1},f_{i+1})$ の間にある場合、次の式が成り立ちます。

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

小課題 $3$ の得点は $30f(Q)$、小課題 $4$ の得点は $60f(Q)$ です。最終得点は小数第 $3$ 位までに四捨五入されます。

時間制限：$10\ \mathrm{s}$。

メモリ制限：$512\ \mathrm{MiB}$。