17705번 - Memory2 서브태스크다국어언어 제한함수 구현

表に 0 以上 N − 1 以下の整数が 1 つ書かれたカードが 2 枚ずつある．あなたと JOI 君は，これら 2N 枚 のカードを用いて神経衰弱というゲームの練習をしている．

ゲームの練習を始める時点では，カードは裏向きの状態でテーブルに横一列に並べられている．左から i + 1 枚目 (0 ≦ i ≦ 2N − 1) のカードを，カード i と呼ぶ．カード i の表に書かれた整数を A_i (0 ≦ i ≦ 2N − 1) とする．最初，JOI 君とあなたには，A_i (0 ≦ i ≦ 2N − 1) がどのような値であるかは分からない． あなたと JOI 君は，以下のやりとりを K 回まで繰り返すことができる．

1. あなたは，2N 枚のカードのうちの 2 枚のカードを指定する．
2. JOI 君は，指定された 2 枚のカードをめくり，表に書かれた整数をあなたに見えないようにこっそり 見る．もし，2 枚のカードの表に書かれた整数が等しい場合は，その値を覚えてあなたに伝える．そ うでない場合は，表に書かれている整数のうち JOI 君が覚えやすい方の整数を覚えてあなたに伝える．

JOI 君にとっての整数の覚えやすさは，N 個の整数 P₀, P₁, . . . , P_N−1 で表される．これらの整数は，以下 の 2 つの条件を満たす．

• 0 ≦ P_i ≦ N − 1 (0 ≦ i ≦ N − 1)．
• P_i ≠ P_j (0 ≦ i < j ≦ N − 1)．

JOI 君にとって i が j よりも覚えやすいことは，P_i < P_j が成り立つことと同値である．

あなたの課題は，JOI 君と K 回以下のやりとりを行うことで，それぞれのカードに書かれた整数を特定 することである．ただし，あなたは，JOI 君にとっての整数の覚えやすさを表す整数 P₀, P₁, . . . , P_N−1 がど のような値であるかを知らない．

JOI 君とやりとりを行って，それぞれのカードに書かれた整数を特定するプログラムを作成せよ．

あなたは，それぞれのカードに書かれた整数を特定する方法を実装した 1 個のプログラムを書かねばな らない．プログラムは Memory2_lib.h をインクルードすること．

プログラムは，以下のルーチンを実装しなければならない．

• void Solve(int T, int N)
  このルーチンは，各テストケースに対し 1 回だけ呼び出される．引数 T は小課題の番号を表し，N は カードが 2N 枚あることを表す．
  このルーチンは，Flip を呼び出すことによってカードに書かれた整数を特定し，その内容を Answer を呼び出すことによって答えなければならない．

プログラム中では以下の関数を呼び出すことができる．

• int Flip(int I, int J)
  この関数は，JOI 君にカードを指定する際に呼び出す．引数 I, J は，JOI 君がめくるカードの番号 I, Jである．
  I と J はともに 0 以上 2N − 1 以下の互いに異なる整数でなければならない．これを満たさない引数とともに Flip を呼び出した場合は b となる．
  この関数は，整数 A_I と整数 A_J が等しい場合はその値を，そうでない場合は整数 A_I と整数 A_J のうち JOI 君にとって覚えやすい方の値を返す．
  この関数を K 回を超えて呼び出した場合は 不正解 [2] となる．
• void Answer(int I, int J, int X)
  この関数は，表に整数 X が書かれたカードの番号を特定できたことを表す．
  引数 I, J, X は，以下の条件を満たしていなければならない．
  • 0 ≦ I ≦ 2N − 1．
  • 0 ≦ J ≦ 2N − 1．
  • I ≠ J．
  • A_I = A_J = X．

これらを満たさない引数とともに Answer を呼び出した場合は 不正解 [3] となる．

引数 X は，以前のどの呼び出しにおける引数 X とも異ならなければならない．これが満たされない場合は 不正解 [4] となる．

この関数は，ちょうど N 回呼び出さなければならない．これが満たされない場合は 不正解 [5] となる．

内部での使用のために他のルーチンを実装したり，グローバル変数を宣言したりするのは自由である．ただし，あなたの提出は標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．

• 1 ≦ N ≦ 50．
• 0 ≦ P_i ≦ N − 1 (0 ≦ i ≦ N − 1)．
• P_i ≠ P_j (0 ≦ i < j ≦ N − 1)．
• 0 ≦ A_i ≦ N − 1 (0 ≦ i ≦ 2N − 1)．
• どの x (0 ≦ x ≦ N − 1) に対しても，A_i = x を満たす i (0 ≦ i ≦ 2N − 1) はちょうど 2 つある．

• T = 1．
• K = 10 000．
• P_i = i (0 ≦ i ≦ N − 1)．

• T = 2．
• K = 400．
• P_i = i (0 ≦ i ≦ N − 1)．

• T = 3．
• K = 300．

採点プログラムのサンプルが読み込む入力の例と，それに対応するルーチンの呼び出しの例を以下に示す．

1 3 10000
0 1 2
1 0 2 0 1 2

この例での関数の呼び出しは，必ずしも意味のある呼び出しとは限らないことに注意せよ．

• dist.zip