JOIG 2025/2026 ファイナルステージ過去問

A - マカロン (Macaron)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

JOI マーケットで K 種類のマカロンが発売された．このマカロンは箱詰めで売られている．

マカロンの箱詰めでは，N 個のマカロンが箱の中で左右一列に並んでおり，左から i 個目 (1 \leqq i \leqq N) のマカロンの種類は A_i である．

ビ太郎はマカロンの箱詰めを購入した．

ビバ子もマカロンを狙っている．ビバ子にマカロンを食べられたくないビ太郎は，ある連続した高々 1 つの区間にシートを張り，その区間のマカロンを見えなくすることにした．左から l 個目のマカロンから，左から r 個目のマカロンまでの区間にシートを張るとき (1 \leqq l \leqq r \leqq N)，そのシートの長さは r - l + 1 である．

ビバ子は K種類のマカロンすべてが見えるという状態でない場合，マカロンの箱詰めに手を出さない．

ビ太郎はできるだけ短いシートを張ることで，ビバ子がマカロンの箱詰めに手を出さないようにしたい．マカロンの箱の情報が与えられたとき，ビ太郎が張る必要のあるシートの長さの最小値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N K 
A_1 A_2 \cdots A_N

出力

標準出力に，ビ太郎が張る必要があるシートの長さの最小値を 1 行で出力せよ．ただし，シートを張る必要がない場合は 0 を出力せよ．

制約

1 \leqq K \leqq N \leqq 500\,000．
1 \leqq A_i \leqq K (1 \leqq i \leqq N)．
入力される値はすべて整数である．

小課題

(20 点) N \leqq 100．
(30 点) K \leqq 100．
(50 点) 追加の制約はない．

入力例 1

7 3
1 3 2 3 1 2 3

出力例 1

例えば，左から 3 個目から 6 個目までのマカロンを見えなくするように長さ 4 のシートを張ると，種類が 2 のマカロンは 1 つも見えなくなるため，ビバ子はマカロンの箱詰めに手を出さない．

これより短いシートで，ビバ子がマカロンの箱詰めに手を出さないようにすることはできない．したがって，4 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

7 4
1 3 4 4 1 3 1

出力例 2

ビ太郎が購入したマカロンの箱詰めには，最初から種類が 2 のマカロンがないため，シートを張らなくてもビバ子はマカロンの箱詰めに手を出さない．

したがって，0 を出力する．

この入力例はすべての小課題の制約を満たす．

B - 運動会 (Sports Festival)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

JOIG 高校には，1 から N までの番号が付けられた N 個のクラスがある．

今日は JOIG 高校の運動会で，最後の競技を残すのみとなった．最後の競技が始まる直前でのクラス i (1\leqq i \leqq N) の得点は A_i である．最後の競技では，N 個のクラスすべてが出場し，各クラスに 1 位から N 位までの相異なる順位が付けられる．

最後の競技では， j (1\leqq j \leqq N) 位のクラスの得点に N - j + 1 点が加算され，その後最終的な順位が決定される．最終的な順位は，得点の高いクラスが上の順位となり，同点の場合はクラスの番号が小さい方が上の順位となる．

JOIG 高校の運動会実行委員である葵さんは，競技終了後各クラスに授与する賞状を予め作っておきたいと考えている．そこで，最終的に各クラスが何種類の順位を取りうるか知りたい．

最後の競技が終わった後，各クラスが取りうる最終的な順位の種類数を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N

出力

標準出力に N 個の整数を空白区切りで，1 行で出力せよ． i (1\leqq i \leqq N) 番目に出力する整数は，クラス i が取りうる最終的な順位の種類数とせよ．

制約

1 \leqq N \leqq 1\,000\,000．
1 \leqq A_i \leqq 10^9 (1\leqq i \leqq N)．
入力される値はすべて整数である．

小課題

(12 点) N \leqq 9．
(27 点) N \leqq 300．
(21 点) N \leqq 5\,000．
(29 点) N \leqq 200\,000．
(11 点) 追加の制約はない．

入力例 1

4
5 2 3 6

出力例 1

3 2 3 3

例として，最後の競技の結果がクラスの番号順に 2 位，3 位，1 位，4 位である場合を考える．それぞれのクラスの得点に 3 点，2 点，4 点，1 点が加算されるため，最終的な得点は順に 8 点，4 点，7 点，7 点となる．したがって，最終的な順位はそれぞれ 1 位，4 位，2 位，3 位となる．

このように，最後の競技の順位としてありうるものすべてを考慮したとき，各クラスが取りうる最終的な順位は以下のようになる．

クラス 1 が取りうる最終的な順位は 1 位，2 位，3 位の 3 種類である．
クラス 2 が取りうる最終的な順位は 3 位，4 位の 2 種類である．
クラス 3 が取りうる最終的な順位は 2 位，3 位，4 位の 3 種類である．
クラス 4 が取りうる最終的な順位は 1 位，2 位，3 位の 3 種類である．

この入力例はすべての小課題の制約を満たす．

入力例 2

3
1000000000 1 1

出力例 2

1 2 2

クラス 1 は最後の競技結果によらず最終的な順位が 1 位となるため，1 番目には 1 を出力する．

クラス 2 とクラス 3 は，最後の競技で上の順位を取ったほうが 2 位，下の順位を取ったほうが 3 位となるため，2 番目と 3 番目にはそれぞれ 2 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 3

7
11 10 17 10 15 7 11

出力例 3

7 6 3 6 5 4 6

この入力例はすべての小課題の制約を満たす．

C - ケーキの飾りつけ (Cake 4)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

JOI くんと IOI ちゃんは兄妹であり，今日は IOI ちゃんの誕生日である．JOI くんは IOI ちゃんの誕生日を祝うために N 個のケーキを購入した．ケーキには 1 から N までの番号が付けられており，ケーキ i (1 \leqq i \leqq N) の大きさは A_i である． JOI くんは IOI ちゃんを喜ばせようと考え，N 個の計画を立てた．i 番目 (1 \leqq i \leqq N) の計画は，ケーキ i に甘さ V_i のいちごを 1 個飾りつけることである．

JOI くんはケーキの見栄えにもこだわりがあるため，以下の条件をすべて満たすように 0 個以上のいくつかの計画を選んで実行する．

いちごが飾りつけられた相異なる 2 つのケーキについて，それらのケーキの大きさの和は S ではない．
いちごが飾りつけられた相異なる 2 つのケーキについて，それらのケーキの大きさの差は D ではない．

実行する計画の個数が 1 つ以下のとき，条件は必ず満たされることに注意せよ．

IOI ちゃんは甘いものが好物であるため，飾りつけられたいちごの甘さの合計をなるべく大きくしたい．ここで，1 つもいちごを飾りつけなかった場合，飾りつけられたいちごの甘さの合計は 0 とする．

ケーキといちごの情報が与えられたとき，飾りつけられたいちごの甘さの合計としてありうる最大値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N S D
A_1 A_2 \cdots A_N
V_1 V_2 \cdots V_N

出力

標準出力に，飾りつけられたいちごの甘さの合計としてありうる最大値を 1 行で出力せよ．

制約

1 \leqq N \leqq 200\,000．
1 \leqq S \leqq 10^9．
1 \leqq D \leqq 10^9．
1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
1 \leqq V_i \leqq 10^9 (1 \leqq i \leqq N)．
入力される値はすべて整数である．

小課題

(7 点) N \leqq 20．
(14 点) S \leqq 40，D \leqq 20，A_i \leqq 20 (1 \leqq i \leqq N)．
(18 点) S = 1．
(30 点) D = 1，S は奇数．
(15 点) D = 1．
(16 点) 追加の制約はない．

入力例 1

5 8 3
3 4 5 6 7
10 6 7 5 4

出力例 1

計画 2,3,4 を選び，実行することを考える．いちごが飾りつけられたケーキ 2,3,4 の中からどのように相異なる 2 つを選んでも，大きさの和が 8 となることや差が 3 となることはない．したがって，これらの計画は実行可能である．ここで，飾りつけられたいちごの甘さの合計は 6 + 7 + 5 = 18 となる．

甘さの合計が 18 より大きくなるような計画の選び方は存在しないため，18 を出力する．

この入力例は小課題 1,2,6 の制約を満たす．

入力例 2

3 1 3
4 7 10
3 10 8

出力例 2

この入力例は小課題 1,2,3,6 の制約を満たす．

入力例 3

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

出力例 3

この入力例はすべての小課題の制約を満たす．

D - カジノ (Casino)

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点： 100 点

配布ファイル

AtCoder での提出方法

Azzurro.h, Bordeaux.h を include し，問題文で指定された関数を実装してください．

標準入出力やファイルへの入出力を使用しないでください．

問題文

イタリアのカジノを訪れた Azzurro と Bordeaux の 2 人組は，ディーラーの Chiaro に提案されたゲームを遊ぶことにした．

このゲームでは，N 行 N 列 (N = 8) のマス目を介して情報を伝える．マス目の各行には上から順に 0 から N - 1 までの行番号が，各列には左から順に 0 から N - 1 までの列番号が付けられている．行番号が r であり，列番号が c であるマスを (r, c) と表記する．

このゲームでは，Azzurro と Bordeaux が別々の部屋に隔離された状態で Q 回のターンが行われる．i 回目 (1 \leqq i \leqq Q) のターンは次のように進行する．

Azzurro は Chiaro から，整数 N, L_i (1 \leqq L_i \leqq 51) および 'A' と 'B' からなる L_i 文字の文字列 S_i が書かれたカードと，すべてのマスが白色で塗られた N 行 N 列のマス目を受け取る．
Azzurro は，N^2 個のマスについて，各マスを青色か赤色で塗る．その後，Chiaro にマス目を渡す．
Chiaro は，以下の操作を Azzurro と Bordeaux から見えない場所で行う．
1. 下または右に隣接するマスへの移動のみを繰り返して (0, 0) から (N - 1, N - 1) まで到達する経路を 1 つ選ぶ．
2. 経路上にあるすべてのマスについて，そのマスが青色で塗られているならば赤色で塗り直し，赤色で塗られているならば青色で塗り直す．
Bordeaux は Chiaro から，整数 N, L_i が書かれたカードとマス目を受け取る．
Bordeaux は 'A' と 'B' からなる L_i 文字の文字列を紙に書く．書いた文字列が S_i と一致していれば，Azzurro と Bordeaux の勝利となる．

Azzurro と Bordeaux がこのゲームで勝利するための戦略を実装せよ．なお，この課題の採点方法については，採点基準の項を参照すること．

実装の詳細

あなたは 2 つのファイルを提出しなければならない．

1 つ目のファイルは Azzurro.cpp という名前である．このファイルは Azzurro の戦略を実装したファイルであり，以下の関数を実装していなければならない．また，#include プリプロセッサ指令によって Azzurro.h を読み込むこと．

std::vector<std::vector<int>> Azzurro(int N, int L, std::string S) この関数は合計 Q 回呼び出される．i 回目 (1 \leqq i \leqq Q) の呼び出しは，ゲームにおける i 回目のターンの手順 1.，手順 2. に相当する．
- 引数 N は i 回目のターンの手順 1. で Azzurro が受け取るカードに書かれた整数 N である．
- 引数 L は i 回目のターンの手順 1. で Azzurro が受け取るカードに書かれた整数 L_i である．
- 引数 S は i 回目のターンの手順 1. で Azzurro が受け取るカードに書かれた文字列 S_i である．
関数 Azzurro の 1 回の呼び出しについて，各要素が 0 または 1 である N \times N の 2 次元配列 \texttt{x} を返さなければならない．これが満たされない場合，不正解 [1] と判定される．
- \texttt{x}[\texttt{r}][\texttt{c}] = 0 (0 \leqq \texttt{r} \leqq N - 1，0 \leqq \texttt{c} \leqq N - 1) のとき，マス (\texttt{r}, \texttt{c}) を青色で塗ることを表す．
- \texttt{x}[\texttt{r}][\texttt{c}] = 1 (0 \leqq \texttt{r} \leqq N - 1，0 \leqq \texttt{c} \leqq N - 1) のとき，マス (\texttt{r}, \texttt{c}) を赤色で塗ることを表す．

2 つ目のファイルは Bordeaux.cpp という名前である．このファイルは Bordeaux の戦略を実装したファイルであり，以下の関数を実装していなければならない．また，#include プリプロセッサ指令によって Bordeaux.h を読み込むこと．

std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T) この関数は Azzurro がマス目を塗り終わるたびに 1 回，合計で Q 回呼び出される．i 回目 (1 \leqq i \leqq Q) の呼び出しは，ゲームにおける i 回目のターンの手順 4.，手順 5. に相当する．
- 引数 N は，i 回目のターンの手順 4. で Bordeaux が受け取るカードに書かれた整数 N である．
- 引数 L は，i 回目のターンの手順 4. で Bordeaux が受け取るカードに書かれた整数 L_i である．
- 引数 T は，i 回目のターンの手順 4. で Bordeaux が受け取るマス目の各マスの色を表す N \times N の 2 次元配列である．マス (\texttt{r}, \texttt{c}) (0 \leqq \texttt{r} \leqq N - 1，0 \leqq \texttt{c} \leqq N - 1) の色は，\texttt{T[r][c]} = 0 であれば青色，\texttt{T[r][c]} = 1 であれば赤色である．
関数 Bordeaux の 1 回の呼び出しについて，'A' と 'B' からなる L_i 文字の文字列 s を返さなければならない．これが満たされない場合，不正解 [2] と判定される．

重要な注意

内部での使用のために他の関数を実装したり，グローバル変数を宣言するのは自由である．ただし，提出された 2 つのプログラムは，採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので，各ファイル内のすべてのグローバル変数と内部関数を無名名前空間内で宣言して，他のファイルとの干渉を避ける必要がある．採点時には，このプログラムは Azzurro 側，Bordeaux 側として 2 個のプロセスとして実行されるので， Azzurro 側と Bordeaux 側でプログラム中のグローバル変数を共有することはできない．
あなたの提出したプログラムは，標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．ただし，標準エラー出力にデバッグ情報等を出力することは許される．

コンパイル・実行の方法

作成したプログラムをテストするための，採点プログラムのサンプルが，コンテストサイトからダウンロードできるアーカイブの中に含まれている．このアーカイブには，提出しなければならないファイルのサンプルも含まれている．

採点プログラムのサンプルは 1 つのファイルからなる．そのファイルは grader.cpp である．作成したプログラムをテストするには，grader.cpp，Azzurro.cpp，Bordeaux.cpp，Azzurro.h，Bordeaux.h を同じディレクトリに置き，次のようにコマンドを実行する．

g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp

なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．その場合，次のようにコマンドを実行する．

./compile.sh

コンパイルが成功すれば，grader という実行ファイルが生成される．

実際の採点プログラムは，採点プログラムのサンプルとは異なることに注意すること．採点プログラムのサンプルは単一のプロセスとして起動する．このプログラムは，標準入力から入力を読み込み，標準出力に結果を出力する．

なお，実際の採点プログラムにおいて，Chiaro の選ぶ経路はあらかじめ定まっている．すなわち，あなたの提出したプログラムにおける関数 Azzurro や関数 Bordeaux が呼び出される前に，Chiaro の選ぶ経路は確定している．

採点プログラムのサンプルの入力

採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む．

Q N 
L_1 
S_1 
R_1 
L_2 
S_2 
R_2 
\vdots 
L_Q 
S_Q 
R_Q

ここで，R_i (1 \leqq i \leqq Q) は，'D' と 'R' を N - 1 文字ずつ含む 2(N - 1) 文字の文字列である．この文字列は Chiaro が i 回目のターンで選ぶ，下または右に隣接するマスへの移動のみを繰り返して (0, 0) から (N - 1, N - 1) まで到達する経路を表す．その経路は，(0, 0) からスタートして，j = 1, 2, \cdots , 2(N - 1) の順に，R_i の j 文字目が 'D' であれば下に隣接するマスに，'R' であれば右に隣接するマスに移動する，という操作を繰り返すことで最終的に (N - 1, N - 1) に到達する経路である．

採点プログラムのサンプルの出力

採点プログラムのサンプルは標準出力へ以下の情報を出力する（引用符は実際には出力されない）．

正解の場合，L^{*} の値が "Accepted: 26" のように出力される．L^{*} の値については採点基準の項を参照せよ．
不正解の場合，不正解の種類が "Wrong Answer [1]" のように出力される．

実行するプログラムが複数の不正解の条件を満たした場合，表示される不正解の種類はそれらのうち 1 つのみである．採点プログラムのサンプルは，不正解の条件を満たした場合，途中で実行を打ち切ることがある．

制約

すべての入力データは以下の条件を満たす．

1 \leqq Q \leqq 30\,000．
N = 8．
1 \leqq L_i \leqq 51 (1 \leqq i \leqq Q)．
Q, L_i (1 \leqq i \leqq Q) は整数である．
S_i (1 \leqq i \leqq Q) は 'A' と 'B' からなる L_i 文字の文字列である．
R_i (1 \leqq i \leqq Q) は 'D' と 'R' を N - 1 文字ずつ含む 2(N - 1) 文字の文字列である．

採点基準

この課題のテストケースの中で，1 つでも不正解 [1] または不正解 [2]（実装の詳細を参照）と判定されたものや，実行時エラー（実行時間制限超過，メモリ制限違反，異常終了など）と判定されたものがあった場合，他のテストケースでどのターンに勝利したかにかかわらず無条件で 0 点となる．

そうでない場合，この課題のすべてのテストケースに対する以下の値の最小値を L^{*} とするとき，下表のように得点が与えられる．

L_i \leqq L を満たすすべてのターンについて勝利したような最大の整数 L．ただし，テストケース内のすべてのターンに勝利した場合は L = 51 とする．

やりとりの例

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

入力例 1

2 2
1
B
RD
3
ABB
DR

この入力例は Q \ (= 2) 回のターンからなり，2 回のターンでは N 行 N 列 (N = 2) のマス目を使用する．この例では，1 回目のターンは次のように進行する．

Azzurro は (0, 1) と (1, 0) を青色に，(0, 0) と (1, 1) を赤色に塗る．その後，Chiaro にマス目を渡す．
Chiaro は，以下の操作を Azzurro と Bordeaux から見えない場所で行う．
1. 下または右に隣接するマスへの移動のみを繰り返して (0, 0) から (N - 1, N - 1) まで到達する経路として，(0, 0) \rightarrow (0, 1) \rightarrow (1, 1) を選ぶ．
2. この経路上にある 3 つのマス (0, 0), (0, 1), (1, 1) について，そのマスに塗られた色を変更する．これにより，(0, 0), (0, 1), (1, 1) の色はそれぞれ青色，赤色，青色に変更される．
Bordeaux は "B" と紙に書くことで，このターンでは勝利できる．

また，2 回目のターンは次のように進行する．

Azzurro はすべてのマスを青色に塗る．その後，Chiaro にマス目を渡す．
Chiaro は，以下の操作を Azzurro と Bordeaux から見えない場所で行う．
1. 下または右に隣接するマスへの移動のみを繰り返して (0, 0) から (N - 1, N - 1) まで到達する経路として，(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) を選ぶ．
2. この経路上にある 3 つのマス (0, 0), (1, 0), (1, 1) について，そのマスに塗られた色を変更する．これにより，(0, 0), (1, 0), (1, 1) の色はすべて赤色に変更される．
Bordeaux は "ABB" と紙に書くことで，このターンでは勝利できる．

この入力例は制約を満たさないことに注意すること．コンテストサイトからダウンロードできるファイルのうち，sample-01-in.txt は入力例 1 に対応する．コンテストサイトからダウンロードできるファイルのうち，sample-02-in.txtは制約を満たす．

E - 鉄道旅行 4 (Railway Trip 4)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

ローマのとある郊外に，1 本の十分に長い線路がある．この線路は数直線とみなすことができ，線路沿いの各地点は 1 個の整数による座標で表される．この線路に沿って N 個の駅があり，座標の小さい順に 1 から N までの番号が付けられている．駅 i (1 \leqq i \leqq N) の位置は座標 A_i である．2 つ以上の駅が同じ座標に存在することはない．

この線路上を列車が走っている．列車は座標が小さい地点から大きい地点に向かう方向にのみ運行しており，すべての駅に停車する．

運賃は乗車駅と降車駅の距離に応じて決まり，ある整数列 (B_1, B_2, ..., B_K) を用いて以下のように計算される．ここで，1 = B_1 < B_2 < \cdots < B_K が成り立つ．なお，乗車駅と降車駅は相異なる必要がある．

乗車駅と降車駅の距離を d (d\geqq 1) とし，B_j \leqq d を満たす最大の整数 j (1 \leqq j \leqq K) を j_\text{max} とする．このとき，運賃は j_\text{max} である．

イタリア観光に来たビ太郎は，この列車に Q 回乗車する計画があり，各回の運賃を計算しようと思っている． k 回目 (1 \leqq k \leqq Q) の乗車計画では，列車に乗って駅 l_k から駅 r_k まで行きたいと思っている．ここで，l_k < r_k である．

ビ太郎は疲れているので，列車に乗らず駅の間を移動することはしない．しかし，途中下車して運賃を一度精算し，再度その駅から乗車することはできる．途中下車はどの駅でも可能であり，回数に制限はない．例えば，駅 s_1, s_2, \cdots, s_m で途中下車した場合 (l_k < s_1 < s_2 < \cdots < s_m < r_k)，距離 A_{s_1} - A_{l_k}, A_{s_2} - A_{s_1}, A_{s_3} - A_{s_2}, \cdots, A_{s_m} - A_{s_{m-1}}, A_{r_k} - A_{s_m} の分の運賃を支払うことになる．

ビ太郎は適切に途中下車することで，駅 l_k から駅 r_k まで行くのに必要な運賃の合計を最小化したい．

駅と運賃と乗車計画の情報が与えられたとき，それぞれの乗車計画について，ビ太郎が支払う必要のある運賃の合計の最小値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N 
A_1 A_2 \cdots A_{N} 
K 
B_1 B_2 \cdots B_{K} 
Q 
l_1 r_1 
l_2 r_2 
\vdots 
l_Q r_Q

出力

標準出力に Q 行出力せよ．k 行目 (1 \leqq k \leqq Q) には k 回目の乗車計画についてビ太郎が支払う必要のある運賃の合計の最小値を出力せよ．

制約

2 \leqq N \leqq 150\,000．
1 \leqq A_1 < A_2 < \cdots < A_N \leqq 10^9．
1 \leqq K \leqq 20．
1 = B_1 < B_2 < \cdots < B_K \leqq 10^9．
1 \leqq Q \leqq 150\,000．
1 \leqq l_k < r_k \leqq N (1 \leqq k \leqq Q)．
入力される値はすべて整数である．

小課題

(8 点) K \leqq 2．
(11 点) N \leqq 500．
(29 点) Q = 1．
(20 点) K \leqq 5．
(32 点) 追加の制約はない．

入力例 1

8
1 3 4 5 8 9 12 14
8
1 2 5 6 7 9 10 11
3
1 5
3 5
1 7

出力例 1

4
2
6

1 回目の乗車計画では，ビ太郎は列車に乗って駅 l_1=1 から駅 r_1=5 まで行きたいと思っている．このとき，例えば以下のように行動することができる．

まず，駅 1 で乗車し，駅 3 で途中下車する．このときの乗車距離は A_3 - A_1 = 3 であり，B_j \leqq 3 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．
次に，駅 3 で再度乗車し，駅 5 で降車する．このときの乗車距離は A_5 - A_3 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．

この場合の運賃の合計は 2 + 2 = 4 であり，これより運賃の合計を小さくすることはできない．よって，1 行目に 4 を出力する．

2 回目の乗車計画では，ビ太郎は列車に乗って駅 l_2=3 から駅 r_2=5 まで行きたいと思っている．このとき，例えば以下のように行動することができる．

駅 3 で乗車し，駅 5 で下車する．このときの乗車距離は A_5 - A_3 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．

この場合の運賃の合計は 2 であり，これより運賃の合計を小さくすることはできない．よって，2 行目に 2 を出力する．

3 回目の乗車計画では，ビ太郎は列車に乗って駅 l_3=1 から駅 r_3=7 まで行きたいと思っている．このとき，例えば以下のように行動することができる．

まず，駅 1 で乗車し，駅 4 で途中下車する．このときの乗車距離は A_4 - A_1 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．
次に，駅 4 で再度乗車し，駅 6 で途中下車する．このときの乗車距離は A_6 - A_4 = 4 であり，B_j \leqq 4 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．
次に，駅 6 で再度乗車し，駅 7 で降車する．このときの乗車距離は A_7 - A_6 = 3 であり，B_j \leqq 3 を満たす最大の整数 j (1 \leqq j \leqq K) は 2 であるので，運賃は 2 である．

この場合の運賃の合計は 2 + 2 + 2 = 6 であり，これより運賃の合計を小さくすることはできない．よって，3 行目に 6 を出力する．

この入力例は小課題 2,5 の制約を満たす．

入力例 2

10
3 6 16 19 32 40 41 53 59 78
2
1 15
1
3 10

出力例 2

この入力例はすべての小課題の制約を満たす．

入力例 3

10
11 13 39 42 53 54 66 69 77 83
15
1 5 13 31 40 41 52 57 59 66 70 79 97 103 115
5
1 6
2 9
1 8
2 7
3 9

出力例 3

この入力例は小課題 2,5 の制約を満たす．

F - 動物園 (Zoo)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

配布ファイル

問題文

あなたは動物園で N 匹のビーバーを飼育している．ビーバーには 0 から N-1 までの番号が付けられている．

この動物園のビーバーはリンゴを食べる．それぞれのビーバーにはリンゴの好みがあり，ビーバー i (0 \leqq i \leqq N-1) は重さ L_i グラム以上 R_i グラム以下のリンゴを好む．ただし，あなたはそれぞれの L_i と R_i の具体的な値を知らない．

あなたは今から N 匹のビーバーの中から K 匹を選び展示ゾーンに入れようと考えている．ただし，次の条件を満たすようなビーバー i とビーバー j (0 \leqq i < j \leqq N-1) が同時に展示ゾーンに入ると，この 2 匹はけんかを始めてしまう．

ビーバー i とビーバー j が両方とも好む重さのリンゴが存在する．つまり，L_i \leqq x \leqq R_i かつ L_j \leqq x \leqq R_j を満たす実数 x が存在する．

あなたは以前の経験からこのような (i, j) の組が存在しないように K 匹のビーバーを選ぶことができることを覚えていたが，肝心のビーバーの選び方を忘れてしまった．

あなたは以下の形式の質問を 1\,000 回まで行うことができる．

0 以上 N 以下の整数 m および，0 以上 N-1 以下の互いに異なる m 個の整数 t_0, t_1, \ldots, t_{m-1} を指定する． m 匹のビーバー t_0, t_1, \ldots, t_{m-1} のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーをけんかが起きないように展示ゾーンに入れることができるかを尋ねる．

あなたは質問を行うことで，具体的にビーバーを K 匹選んで展示ゾーンに入れる方法を一つ見つけたい．さらに，質問の回数はなるべく少なくしたい．

ビーバーの数 N と展示ゾーンに入れるビーバーの数 K が与えられたとき，1\,000 回以下の質問で，ビーバーを K 匹選んで展示ゾーンに入れる方法を一つ見つけるプログラムを作成せよ．

入出力

この問題はインタラクティブ問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）である．

最初に，ビーバーの数 N と展示ゾーンに入れるビーバーの数 K が以下の形式で標準入力から与えられる．

N K

あなたのプログラムはこれを受け取った後，採点プログラムとやり取りを行わなければならない．

1 回の質問を行うには，以下の形式で採点プログラムとやり取りせよ．

まず，以下の形式で標準出力に出力せよ．
```
? m t_0 t_1 \ldots t_{m-1}
```
- m は 0 以上 N 以下の整数である．これが満たされていない場合，不正解[1] と判定される．
- その後に続く m 個の整数 t_0, t_1, \ldots, t_{m-1} は 0 以上 N-1 以下の互いに異なる整数である．これが満たされていない場合，不正解[2] と判定される．
その後，質問の回答を表す整数 r が以下の形式で標準入力から与えられる．
```
r
```
ここで r は -1 以上 N 以下の整数である． r = -1 であるとき，採点プログラムがあなたのプログラムを不正解であると判定したことを表す． この場合，ただちにあなたのプログラムを終了せよ． 0 \leqq r \leqq N であるとき，m 匹のビーバー t_0, t_1, \ldots, t_{m-1} のみから展示ゾーンに入れるビーバーを選ぶとき，最大で r 匹のビーバーをけんかが起きないように展示ゾーンに入れることができることを表す．r > K である場合もあることに注意せよ．

質問は 1\,000 回を超えて行ってはならない．1\,000 回を超えて行った場合，不正解[3] と判定される．

ビーバーを K 匹選んで展示ゾーンに入れる方法を一つ回答するには，以下の形式で標準出力に出力せよ．

! s_0 s_1 \ldots s_{K-1}

K 個の整数 s_0, s_1, \ldots, s_{K-1} は，K 匹のビーバー s_0, s_1, \ldots, s_{K-1} を展示ゾーンに入れることを表す．
s_0, s_1, \ldots, s_{K-1} は 0 以上 N - 1 以下の互いに異なる整数でなければならない．これが満たされていない場合，不正解[4] と判定される．
ビーバー s_0, s_1, \ldots, s_{K-1} を展示ゾーンに入れるとけんかが起きる場合，不正解[5] と判定される．
回答は丁度 1 回行わなければならない．2 回以上回答した場合，不正解[6] と判定される．あなたのプログラムの終了時に回答が 1 回も行われていなかった場合，不正解[7] と判定される．

上にあげたいずれでもない形式で標準出力に出力した場合，不正解[8] と判定される．

重要な注意

各出力の最後には，必ず標準出力を flush せよ．flush しない場合，実行時間制限超過と判定される可能性がある．
- C++ のプログラムを提出する場合，cout << endl; によって，改行されるとともに自動的に flush される．もし printf を使用する場合，fflush(stdout); を用いよ．
- Python のプログラムを提出する場合，入力に input() を使う限り自動的に flush される．
質問の際に -1 を受け取った場合，ただちにプログラムを終了せよ．終了しなかった場合，実行結果は不定である．

採点に関する注意

実際の採点プログラムは適応的 (adaptive) ではなく，やりとりの初めから固定された答えを持つ．

テストツール

作成したプログラムをテストするためのテストツール testing_tool.py が，コンテストサイトからダウンロードできるアーカイブの中に含まれている．このツールを必ずしも使う必要はなく，また変更することも許される．実際の採点プログラムはテストツールとは異なることに注意すること．

あなたが C++ で作成したプログラムをテストするには，以下のような手順に従えばよい．

あなたのプログラムをコンパイルして実行ファイルを生成せよ．例えば，あなたのプログラムが zoo.cpp という名前の場合，以下のようなコマンドを実行すれば zoo という実行ファイルが生成される．
```
g++ -std=gnu++20 -O2 -o zoo zoo.cpp
```
次に，以下のコマンドを実行せよ．
```
python3 testing_tool.py ./zoo
```

あなたのプログラムが Python で実装されている場合，例えば，あなたのプログラムが zoo.py という名前なら，以下のコマンドを実行せよ．

python3 testing_tool.py python3 zoo.py

テストツールの入力

テストツールは標準入力から以下の形式で入力を読み込む．

N K 
L_0 R_0 
L_1 R_1 
\vdots 
L_{N-1} R_{N-1}

テストツールの出力

プログラムの実行が正常に終了した場合，テストツールは標準出力へ以下の情報を出力する (引用符は実際には出力されない)．

正解の場合，質問の回数が "Accepted: 22" のように出力される．
不正解の場合，不正解の種類が"Wrong Answer [2]"のように出力される．

実行するプログラムが複数の不正解の条件を満たした場合，表示される不正解の種類はそれらのうち 1 つのみである．

制約

すべての入力データは以下の条件を満たす．

1 \leqq N \leqq 1\,000．
1 \leqq K \leqq \min(10, N)．
1 \leqq L_i \leqq R_i \leqq 10\,000 (0 \leqq i \leqq N-1)．
けんかが起きないように K 匹のビーバーを選ぶ方法が一つ以上存在する．
入力される値はすべて整数である．

小課題

(6 点) N \leqq 8．
(7 点) N \leqq 12．
(14 点) N \leqq 20．
(21 点) N \leqq 50．
(16 点) N \leqq 90．
(36 点) 追加の制約はない．この小課題では，以下に従い得点が決定される．
- 小課題 6 に対応するテストケースに対して，1 つでも不正解があった場合，この小課題の得点は 0 点となる．
- そうでない場合，この小課題のすべてのテストケースにおける，質問の回数の最大値を T とする．このとき，小課題の得点は以下のように決定される．
  - 100 < T \leqq 1\,000 の場合，13 点．
  - T \leqq 100 の場合，36 点．

小課題 1,2,3,4,5 の得点は質問の回数によらない (1\,000 回以下であればよい) が，100 回より多い場合はコンテストサイトにおいて「出力は部分的に正しい」と表記されることがある．

やりとりの例

テストツールが読み込む入力の例と，それに対応するやり取りの例を以下に示す．

入力例 1

1 回目の質問では，ビーバー 0 とビーバー 2 のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーを展示ゾーンに入れることができるかを質問する．ビーバー 0 を選ぶと 1 匹のビーバーを展示ゾーンに入れることができ，これが最大である．したがって，1 が標準入力から与えられる．

2 回目の質問では，ビーバー 1 のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーを展示ゾーンに入れることができるかを質問する．ビーバー 1 を選ぶと 1 匹のビーバーを展示ゾーンに入れることができ，これが最大である．したがって，1 が標準入力から与えられる．

3 回目の質問では，ビーバー 1 とビーバー 2 とビーバー 3 のみから展示ゾーンに入れるビーバーを選ぶとき，最大で何匹のビーバーを展示ゾーンに入れることができるかを質問する．ビーバー 1 とビーバー 3 を選ぶと 2 匹のビーバーを展示ゾーンに入れることができ，これが最大である．したがって，2 が標準入力から与えられる．

最後に，ビーバー 1 とビーバー 3 を展示ゾーンに入れる 2 匹として回答している．

なお，このやりとりはあくまで一例であり，これらの質問から正しい回答を得るために必要な情報が得られているとは限らない．

この入力例はすべての小課題の制約を満たす．

G - かかし 2 (Scarecrows 2)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

JOI 村には，広大な畑がある．この畑は無限に広がる xy 座標平面で表され，x 軸正の向きが東方向，y 軸正の向きが北方向である．

JOI 村の村長は，畑を外敵から守るために，畑にいくつかのかかしを配置しようと考えている．配置されたそれぞれのかかしは，その場所と向きに応じて，平面上の特定の領域を守ることができる．

現在，かかしを配置するための N 個の計画が提案されており，1 から N までの番号が付けられている．計画 i (1\leqq i\leqq N) を実行するために必要なコストは C_i であり，その内容は整数 T_i, X_i, Y_i を用いて以下のように表される．

T_i = 1 のとき，かかし 1 体を点 (X_i,Y_i) に西向きに配置する．このかかしは平面上の x \leqq X_i の領域を守る．
T_i = 2 のとき，かかし 1 体を点 (X_i,Y_i) に東向きに配置する．このかかしは平面上の x \geqq X_i の領域を守る．
T_i = 3 のとき，かかし 1 体を点 (X_i,Y_i) に南向きに配置する．このかかしは平面上の y \leqq Y_i の領域を守る．
T_i = 4 のとき，かかし 1 体を点 (X_i,Y_i) に北向きに配置する．このかかしは平面上の y \geqq Y_i の領域を守る．

村長は，これらの N 個の計画のうちいくつかを選んで実行することで，できるだけ少ない合計コストで，平面上のどの点も K 体以上のかかしによって守られているようにしたいと考えている．ただし，N 個の計画においてかかしを配置する点の座標はすべて相異なることが保証される．

かかしを配置する計画の情報が与えられたとき，いくつかの計画を選んで実行することで平面上のどの点も K 体以上のかかしによって守られているようにすることが可能かどうか判定し，可能な場合は実行する計画の合計コストの最小値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N K
T_1 X_1 Y_1 C_1
T_2 X_2 Y_2 C_2
\vdots
T_{N} X_{N} Y_{N} C_{N}

出力

平面上のどの点も K 体以上のかかしによって守られているように配置するために必要な合計コストの最小値を出力せよ．ただし，条件を満たす計画の選び方が存在しない場合は -1 を出力せよ．

制約

1 \leqq K \leqq N \leqq 6\,000．
T_i は 1, 2, 3, 4 のいずれかである (1 \leqq i \leqq N)．
0 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N)．
0 \leqq Y_i \leqq 10^9 (1 \leqq i \leqq N)．
(X_i, Y_i) \neq (X_j, Y_j) (1 \leqq i < j \leqq N)．
0 \leqq C_i \leqq 10^9 (1 \leqq i \leqq N)．
入力される値はすべて整数である．

小課題

(5 点) K = 1，T_i \leqq 2 (1 \leqq i \leqq N)．
(7 点) K = 1．
(7 点) K \leqq 2．
(22 点) N \leqq 15．
(35 点) N \leqq 500，K \leqq 300．
(24 点) 追加の制約はない．

入力例 1

出力例 1

例えば計画 3,5 を実行すると，以下のようにかかしが配置される．

計画 3 では，かかし 1 体を点 (36,73) に西向きに配置する．コストは 78 である．
計画 5 では，かかし 1 体を点 (15,49) に東向きに配置する．コストは 21 である．

このとき，座標平面上のどの点も 1 体以上のかかしで守られている．例えば，点 (0, 0) は計画 3 で点 (36,73) に西向きに配置したかかしによって守られている．また，合計コストは 78+21=99 である．これより少ない合計コストで平面上のすべての点を 1 体以上のかかしで守ることはできないので，99 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

出力例 2

-1

入力例 1 とは K の値のみが異なる．

座標平面上のすべての点を 3 体以上のかかしによって守ることはできないため，-1 を出力する．

この入力例は小課題 4,5,6 の制約を満たす．

入力例 3

出力例 3

この入力例は小課題 5,6 の制約を満たす．

入力例 4

出力例 4

この入力例は小課題 4,5,6 の制約を満たす．

H - スタンプラリー 5 (Collecting Stamps 5)

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

JOI 君が住む IOI 国には N 個の街があり，1 から N までの番号が付けられている．また，IOI 国には N-1 本の道路があり，1 から N-1 までの番号が付けられている．道路 j (1 \leqq j \leqq N-1) は街 U_j と街 V_j を双方向に結んでいる．どの街からどの街へも何本かの道路を通ることによって移動することができる．

これから IOI 国でスタンプラリーが開催される．それぞれの街には 1 つのスタンプ台が設置される予定である．街 i (1 \leqq i \leqq N) のスタンプ台は時刻 T_i に設置される．

JOI 君はスタンプラリーに参加することにした． JOI 君は時刻 0 にいずれかの街から行動を開始する．また，JOI 君は時刻 0 の時点で体力が D である．

JOI 君は時刻 t に街 i にいるとき，次の行動をとる．

まず，現在いる街に既にスタンプ台が設置されている場合はスタンプを押す．すなわち，T_i \leqq t の場合はスタンプを押す．
次に，スタンプラリーを終了するか別の街に移動するかを選ぶ．ただし，街 i と道路で結ばれた街で，まだ訪れたことのない街が存在し，かつ，現在の体力が 1 以上であるときに限り，別の街に移動することを選ぶことができる．
JOI 君が別の街に移動することを選んだ場合，JOI 君は街 i と道路で結ばれた街のうち，まだ訪れたことのない街 j を選び，移動する．体力が 1 減少し，時刻 t+1 に街 j に到着する．
JOI 君がスタンプラリーを終了することを選んだ場合，それまでに一度以上スタンプを押した場合はスタンプラリー成功となり，その場でプレゼントを受け取ることができる．そうでない場合はスタンプラリー失敗となる．

街の移動にかかる時間以外は無視できるものとする． JOI 君が同じ街に留まることはできないことに注意せよ．

大会の運営者であるあなたは，JOI 君がスタンプラリーに成功した場合のためにそれぞれの街にプレゼントを用意しておく必要があるが，プレゼントの数には限りがあるため，必要最小限の街にプレゼントを用意したい．しかしながら，あなたは JOI 君がどの街から行動を開始するかについての情報を持っていない．そこで，あなたはそれぞれの s (1 \leqq s \leqq N) について，JOI 君が街 s から行動を開始したときに，プレゼントを用意しておく必要のある街の数，すなわち，JOI 君が街 g でスタンプラリーを終了をしたときにスタンプラリー成功となる可能性があるような g (1\leqq g\leqq N) の数を求めたい．

IOI 国の街と道路の情報，JOI 君の体力，およびスタンプ台の設置時刻が与えられたとき，それぞれの街について，その街から JOI 君が行動を開始したときにプレゼントを用意しておく必要のある街の数を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N D
T_1 T_2 \cdots T_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

標準出力に，N 行出力せよ． s 行目 (1\leqq s \leqq N) には，JOI 君が街 s から行動を開始したときにプレゼントを用意しておく必要のある街の数を出力せよ．

制約

2 \leqq N \leqq 400\,000．
0 \leqq D \leqq N-1．
0 \leqq T_i \leqq N (1 \leqq i \leqq N)．
1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq N-1)．
どの街からどの街へも何本かの道路を通ることによって移動することができる．
入力される値はすべて整数である．

小課題

(5 点) D\leqq 1．
(9 点) N\leqq 3\,000，(U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1)．
(17 点) N\leqq 3\,000．
(17 点) (U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1)．
(33 点) D=N-1，N \leqq 150\,000．
(19 点) 追加の制約はない．

入力例 1

出力例 1

s=1 のとき，JOI 君の行動の一例を示す．

JOI 君は時刻 0 に街 1 にいる状態で，次の行動をとる．
- 街 1 にはまだスタンプ台が設置されていないため，JOI 君はスタンプを押さない．
- JOI 君の現在の体力は 2 である．街 1 と道路で結ばれた街のうち，まだ訪れたことのない街の一つである街 2 に移動する．
- JOI 君の体力が 1 減少し，時刻 1 に街 2 に到着する．
JOI 君は時刻 1 に街 2 にいる状態で，次の行動をとる．
- 街 2 にはまだスタンプ台が設置されていないため，JOI 君はスタンプを押さない．
- JOI 君の現在の体力は 1 である．街 2 と道路で結ばれた街のうち，まだ訪れたことのない街の一つである街 3 に移動する．
- JOI 君の体力が 1 減少し，時刻 2 に街 3 に到着する．
JOI 君は時刻 2 に街 3 にいる状態で，次の行動をとる．
- 街 3 には既にスタンプ台が設置されているため，JOI 君はスタンプを押す．
- JOI 君はここでスタンプラリーを終了することを選ぶ．これまでに一度以上スタンプを押しているため，スタンプラリー成功となる．その場でプレゼントを受け取る．

よって，JOI 君が街 1 から行動を開始し，街 3 でスタンプラリーを終了したときにスタンプラリー成功となる可能性があるため，街 3 にプレゼントを用意しておく必要がある． JOI 君が街 1 から行動を開始したときにプレゼントを用意しておく必要のある街は街 3 と街 4 のみであるため，1 行目には 2 を出力する．

また，JOI 君が街 2 から行動を開始したときにプレゼントを用意しておく必要のある街は街 3，街 4 と街 5 のみであるため，2 行目には 3 を出力する．

この入力例は小課題 3,6 の制約を満たす．

入力例 2

出力例 2

この入力例は小課題 1,2,3,4,6 の制約を満たす．

入力例 3

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

出力例 3

この入力例は小課題 3,5,6 の制約を満たす．

I - チーズとネズミ (Cheeses and Mice)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

ネズミの住む巣穴があり，巣穴の前に N 個のチーズが一列に並んでいる．列の先頭から i 番目 (1 \leqq i \leqq N) の位置にあるチーズの大きさは i である．

巣穴の中にはネズミが M 匹住んでおり，1 から M までの番号が付けられている．ネズミ j (1 \leqq j \leqq M) は大きさが A_j 以上のチーズを好む．ここで，A_1 < A_2 < \cdots < A_M が満たされる．

ネズミたちはこれから N 日のあいだ毎日，以下の一連の行動をおこなう．

j = 1, 2, \dots, M の順に，以下の操作をおこなう．
- ネズミ j が好むチーズが列の中に存在するならば，そのうち最も先頭に近い位置にあるものを選び，先頭のチーズと位置を入れ替える．ここで，選んだチーズが先頭にある場合や，好むチーズが存在しない場合は，何もしない．
列の先頭にあるチーズを列から取り除き，巣穴の中に引き入れる．

チーズとネズミの数，およびネズミの好みの情報が与えられたとき，N 日間のそれぞれの日に巣穴の中に引き入れられるチーズの大きさを求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N M
A_1 A_2 \cdots A_{M}

出力

標準出力に N 行出力せよ．

k 行目 (1 \leqq k \leqq N) には，k 日目に巣穴の中に引き入れられるチーズの大きさを出力せよ．

制約

1 \leqq M \leqq N \leqq 300\,000．
1 \leqq A_j \leqq N (1 \leqq j \leqq M)．
A_1 < A_2 < \cdots < A_M．
入力される値はすべて整数である．

小課題

(11 点) N \leqq 300．
(16 点) N \leqq 5\,000．
(35 点) M = 1．
(38 点) 追加の制約はない．

入力例 1

5 2
3 4

出力例 1

以下ではチーズの列の内容を，大きさを先頭から順に並べた数列で表す．はじめ，列は (1,2,3,4,5) である． 5 日間のネズミたちの行動は，以下のように進行する．

ネズミ 1 は大きさ 3 のチーズを選び，列は (3,2,1,4,5) になる．ネズミ 2 は大きさ 4 のチーズを選び，列は (4,2,1,3,5) になる．最後に大きさ 4 のチーズが列から取り除かれ，列は (2,1,3,5) になる．
ネズミ 1 は大きさ 3 のチーズを選び，列は (3,1,2,5) になる．ネズミ 2 は大きさ 5 のチーズを選び，列は (5,1,2,3) になる．最後に大きさ 5 のチーズが列から取り除かれ，列は (1,2,3) になる．
ネズミ 1 は大きさ 3 のチーズを選び，列は (3,2,1) になる．ネズミ 2 は何もしない．最後に大きさ 3 のチーズが列から取り除かれ，列は (2,1) になる．
どちらのネズミも何もしない．大きさ 2 のチーズが列から取り除かれ，列は (1) になる．
どちらのネズミも何もしない．大きさ 1 のチーズが列から取り除かれ，列は空になる．

この入力例は小課題 1,2,4 の制約を満たす．

入力例 2

3 1
2

出力例 2

2
3
1

この入力例はすべての小課題の制約を満たす．

J - カレーライス (Curry and Rice)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

葵は N 種類のカレーと，M 種類のライスを準備した．i 種類目 (1 \leqq i \leqq N) のカレーは A_i 皿分，j 種類目 (1 \leqq j \leqq M) のライスは B_j 皿分ある．1 皿分のカレーと 1 皿分のライスを組み合わせることで，1 皿のカレーライスを作ることができる．

葵はビーバーたちにカレーライスを振る舞うことにした．1 匹のビーバーに対し 1 皿のカレーライスを提供するが，ビーバーたちは大変個性的であるため，同じ種類のカレーライスを 2 匹以上のビーバーが受け取ることはない．ただし，カレーとライスが両方とも同じ種類のとき，かつそのときに限り，同じ種類のカレーライスであるとみなす．

準備したカレーとライスでカレーライスを作るとき，最大で何匹のビーバーがカレーライスを受け取ることができるかを求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N M
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_M

出力

標準出力に，カレーライスを受け取ることのできるビーバーの最大数を 1 行で出力せよ．

制約

1 \leqq N \leqq 500\,000．
1 \leqq M \leqq 500\,000．
1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
1 \leqq B_j \leqq 10^9 (1 \leqq j \leqq M)．
入力される値はすべて整数である．

小課題

(6 点) A_i = 1 (1 \leqq i \leqq N), B_j = 1 (1 \leqq j \leqq M)．
(7 点) N = M = 2．
(12 点) N = 2．
(14 点) A_1 = A_2 = \dots = A_N．
(20 点) A_1 + A_2 + \cdots + A_N \leqq 2\,000，B_1 + B_2 + \cdots + B_M \leqq 2\,000．
(19 点) A_1 + A_2 + \cdots + A_N \leqq 500\,000，B_1 + B_2 + \cdots + B_M \leqq 500\,000．
(22 点) 追加の制約はない．

入力例 1

3 4
2 2 2
4 1 1 1

出力例 1

以下の組み合わせでカレーライスを用意する場合が考えられる．

1 種類目のカレーと 1 種類目のライス
1 種類目のカレーと 2 種類目のライス
2 種類目のカレーと 1 種類目のライス
2 種類目のカレーと 3 種類目のライス
3 種類目のカレーと 1 種類目のライス
3 種類目のカレーと 4 種類目のライス

このとき，6 匹のビーバーがカレーライスを受け取ることができる．また，6 匹より多いビーバーがカレーライスを受け取ることはできない．したがって，6 を出力する．

この入力例は小課題 4,5,6,7 の制約を満たす．

入力例 2

3 4
4 2 4
1 4 3 1

出力例 2

以下の組み合わせでカレーライスを用意する場合が考えられる．

1 種類目のカレーと 1 種類目のライス
1 種類目のカレーと 2 種類目のライス
1 種類目のカレーと 3 種類目のライス
2 種類目のカレーと 2 種類目のライス
2 種類目のカレーと 3 種類目のライス
3 種類目のカレーと 2 種類目のライス
3 種類目のカレーと 3 種類目のライス
3 種類目のカレーと 4 種類目のライス

このとき，8 匹のビーバーがカレーライスを受け取ることができる．また，8 匹より多いビーバーがカレーライスを受け取ることはできない．したがって，8 を出力する．

この入力例は小課題 5,6,7 の制約を満たす．

入力例 3

2 2
1 1000000000
1000000000 1

出力例 3

以下の組み合わせでカレーライスを用意する場合が考えられる．

1 種類目のカレーと 1 種類目のライス
2 種類目のカレーと 1 種類目のライス
2 種類目のカレーと 2 種類目のライス

このとき，3 匹のビーバーがカレーライスを受け取ることができる．また，3 匹より多いビーバーがカレーライスを受け取ることはできない．したがって，3 を出力する．

この入力例は小課題 2,3,5,6,7 の制約を満たす．

K - お菓子詰め (Packing Snacks)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

葵は趣味でお菓子作りをしており，作ったお菓子をよく人に配っている．葵は，JOI 記念日にビ太郎にお菓子をあげる約束をした．

当日，葵は N 個のお菓子を作った．お菓子には種類と大きさが存在し，種類は 1 以上 T 以下の整数で表される．また，これらのお菓子には 1 から N までの番号が付けられている．お菓子 i (1 \leqq i \leqq N) の種類は A_i で，大きさは C_i である．葵は N 個のお菓子のうち，ちょうど M 個のお菓子を選んでビ太郎の家に持っていく．ここで M は 1 以上 N 以下の整数である．

ビ太郎は M 個の袋を持っており，袋には 1 から M までの番号が付けられている．袋 j (1 \leqq j \leqq M) には，種類が B_j でありかつ大きさが D_j 以下であるお菓子を最大 1 個入れることができる．ビ太郎は，葵が持ってきた M 個のお菓子のうち，袋に入れることができたお菓子をすべてもらう．

ビ太郎はできるだけ多くのお菓子をもらいたいため，もらえるお菓子の個数がなるべく多くなるように，持ってきたお菓子を袋に入れる．一方，葵はほかの人にもお菓子を配りたいため，ビ太郎がもらえるお菓子の個数がなるべく少なくなるように，持っていくお菓子を選ぶ．ただし，葵はビ太郎が持っている袋の情報を知っている．

お菓子と袋の情報が与えられたとき，ビ太郎がもらえるお菓子の個数を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

N M T
A_1 C_1
A_2 C_2
\vdots
A_N C_N
B_1 D_1
B_2 D_2
\vdots
B_M D_M

出力

標準出力に，ビ太郎がもらえるお菓子の個数を 1 行で出力せよ．

制約

1 \leqq N \leqq 500\,000．
1 \leqq M \leqq \min(N,5\,000)．
1 \leqq T \leqq N．
1 \leqq A_i \leqq T (1 \leqq i \leqq N)．
1 \leqq C_i \leqq 10^9 (1 \leqq i \leqq N)．
1 \leqq B_j \leqq T (1 \leqq j \leqq M)．
1 \leqq D_j \leqq 10^9 (1 \leqq j \leqq M)．
入力される値はすべて整数である．

小課題

(12 点) T = 1．
(17 点) N \leqq 10．
(9 点) N = M = T，A_i = B_i = i (1 \leqq i \leqq N)．
(36 点) N \leqq 5\,000．
(26 点) 追加の制約はない．

入力例 1

出力例 1

葵がお菓子 1，3，5 を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない．このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 2 個のお菓子をもらうことができる．

お菓子 1 を袋 1 に入れる．
お菓子 5 を袋 2 に入れる．

葵がビ太郎のもらえるお菓子の個数の最大値を 2 より小さくすることはできないため，2 を出力する．

この入力例は小課題 1,2,4,5 の制約を満たす．

入力例 2

出力例 2

葵がお菓子 1，4，5 を持っていくと，ビ太郎がもらえるお菓子の個数が最も少ない．このとき，ビ太郎は以下のようにお菓子を袋に入れることで，最大 1 個のお菓子をもらうことができる．

お菓子 1 を袋 1 に入れる．

葵がビ太郎のもらえるお菓子の個数の最大値を 1 より小さくすることはできないため，1 を出力する．

この入力例は小課題 2,4,5 の制約を満たす．

入力例 3

出力例 3

この入力例は小課題 2,3,4,5 の制約を満たす．

入力例 4

出力例 4

この入力例は小課題 2,4,5 の制約を満たす．

L - 電圧 2 (Voltage 2)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

配布ファイル

問題文

あなたは Just Odd Inventions 社を知っているだろうか？　この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．

JOI 社のとある実験室には，複雑な電気回路がある．回路は N 個の節点と M 本の細長い電気抵抗からなり，節点には 0 から N - 1 までの，電気抵抗には 0 から M - 1 までの番号が付けられている．各節点は「高電圧」または「低電圧」のいずれかの状態に設定することができる．電気抵抗 i (0 \leqq i \leqq M - 1) は節点 A_i から異なる節点 B_i に向けて繋がれており，節点 A_i が「高電圧」，節点 B_i が「低電圧」の状態にあるときにのみ電流が流れる．それ以外の場合には電流は流れない．また，任意の 2 つの節点を繋ぐ電気抵抗は，その向きに関わらず高々 1 本しか存在しない．

JOI 社の研究員であるあなたは，この回路を用いて実験を行うことになった．この回路の電気抵抗はあまりにも細長いため，電気抵抗がどの節点を結んでいるのかを目視で確認することはできない．しかし，各節点の電圧を設定している間，電流が流れている電気抵抗の本数に応じて回路の温度が上昇するという手がかりがある．そこであなたは，電圧を設定した後，回路に触れることで温度を読み取ることにした．あなたは回路の温度を正確に読み取ることはできないが，電圧の設定を 2 回行い，どちらの設定においてより温度が高くなったかを比較することはできる．つまり，電圧の設定を 2 回指定することで，以下のいずれかの情報が得られる．

1 回目の電圧の設定の方が，電流が流れる電気抵抗の本数が多い．
2 回の電圧の設定において，電流が流れる電気抵抗の本数は同じである．
2 回目の電圧の設定の方が，電流が流れる電気抵抗の本数が多い．

あなたの目的は，この温度の比較を繰り返すことで，どの節点からどの節点へ向かう電気抵抗が存在するかをすべて特定することである．あらかじめ，節点の数 N，電気抵抗の本数 M は与えられている．また，電気抵抗は異なる節点を繋いでいること，および任意の 2 つの節点を繋ぐ電気抵抗はその向きに関わらず高々 1 本であることも分かっている．これらの条件のもと，温度の比較によって得られた情報から，回路に存在する電気抵抗が繋ぐ節点のペア (a, b) の集合をすべて特定せよ．ただし，回路の構造によっては，いかなる比較を何回行ったとしても，電気抵抗の繋がりを一意に特定できない場合がある．その場合には，特定不能であることを報告する必要がある．

電気抵抗の劣化を防ぐため，実際に温度を比較するのは 30\,000 回までしか行うことが許されない．

なお，JOI 社がこの奇妙な回路を用いてどのような発明をしているかは，社内でも最高機密であり社長以外の誰も知らない．

回路の節点と電気抵抗の本数が与えられたとき，30\,000 回以下の温度の比較で，回路の電気抵抗を特定するかもしくは特定不能であることを報告するプログラムを作成せよ．

実装の詳細

あなたの回答プログラムは，voltage.h を #include プリプロセッサ指令で読み込み，以下の関数を実装しなければならない．

bool solve(int N, int M)
- この関数は 1 回の実行で 1 回だけ呼び出される．
- 引数 N は回路の節点の数 N である．
- 引数 M は回路の電気抵抗の本数 M である．
- この関数は，いかなる温度の比較を何回行ったとしても電気抵抗の繋がりを一意に特定できない場合には false を，それ以外の場合には true を返さなければならない．
- 電気抵抗の繋がりを特定不能であるのに true を返した場合，不正解[1] と判定される．
- 温度の比較によって回路が特定できるのに false を返した場合，不正解[2] と判定される．

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

int query(std::vector<int> x, std::vector<int> y)
- あなたはこの関数を用いて電圧の設定を 2 回行い，温度を比較できる．
- 引数 x は 1 回目の電圧の設定を，引数 y は 2 回目の電圧の設定を指定する．
- 引数 x と y は 0 と 1 からなる長さ N の配列でなければならない．
- x[k] (0 \leqq k \leqq N - 1) が 1 ならば 1 回目の電圧の設定において，節点 k は「高電圧」に， x[k] が 0 ならば節点 k は「低電圧」に設定することを表す．
- y[k] (0 \leqq k \leqq N - 1) が 1 ならば 2 回目の電圧の設定において，節点 k は「高電圧」に， y[k] が 0 ならば節点 k は「低電圧」に設定することを表す．
- この関数の戻り値は 1 回目の電圧の設定と 2 回目の電圧の設定において，温度を比較した結果であり，-1,0,1のいずれかの値である．
  - 戻り値が-1のとき，1 回目の方が，2 回目の電圧の設定より，電流が流れる電気抵抗の本数が多いことを表す．
  - 戻り値が0のとき，1 回目と2 回目の電圧の設定において電流が流れる電気抵抗の本数が等しいことを表す．
  - 戻り値が1のとき，2 回目の方が，1 回目の電圧の設定より，電流が流れる電気抵抗の本数が多いことを表す．
- 引数 x の長さが N でない場合，不正解[3] と判定される．
- 引数 x に 0 でも 1 でもない値が含まれる場合，不正解[4] と判定される．
- 引数 y の長さが N でない場合，不正解[5] と判定される．
- 引数 y に 0 でも 1 でもない値が含まれる場合，不正解[6] と判定される．
- この関数を 30\,000 回より多く呼び出してはならない．30\,000 回より多く呼び出した場合，不正解[7] と判定される．
void answer(int a, int b)
- この関数を用いて，特定した電気抵抗を解答する．
- 引数 a, b は節点 a から節点 b に向けて繋がれている電気抵抗があることを表す．
- 0 \leqq a \leqq N - 1 かつ 0 \leqq b \leqq N - 1 でなければならない．これが満たされない場合 不正解[8] と判定される．
- 同じ (a, b) の組を引数として 2 回以上呼び出してはならない．これが満たされない場合 不正解[9] と判定される．
- この関数を M 回より多く呼び出してはならない．M 回より多く呼び出した場合，不正解[10] と判定される．
- 関数 solve が true を返したとき，それまでに関数 answer はちょうど M 回呼び出されている必要がある．これが満たされない場合，不正解[11] と判定される．
- 関数 solve が true を返したとき，それまでに関数 answer の引数として渡されたすべての組 (a, b) について，節点 a から節点 b へ向けて繋がれている電気抵抗が実際に存在していなければならない．これが満たされない場合，不正解[12] と判定される．

重要な注意

内部での使用のために他の関数を実装したり，グローバル変数を宣言するのは自由である．
あなたの提出したプログラムは，標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．ただし，標準エラー出力にデバッグ情報等を出力することは許される．

コンパイル・実行の方法

採点プログラムのサンプルは 1 つのファイルからなる. そのファイルは grader.cpp である．作成したプログラムをテストするには，これらのファイル grader.cpp, voltage.cpp, voltage.h を同じディレクトリに置き，次のようにコマンドを実行する．

g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp

なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．その場合，次のようにコマンドを実行する．

./compile.sh

コンパイルが成功すれば，grader という実行ファイルが生成される．

採点プログラムのサンプルの入力

採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む．

N M
A_0 B_0
\vdots
A_{M-1} B_{M-1}

採点プログラムのサンプルの出力

採点プログラムのサンプルは標準出力へ以下の情報を出力する (引用符は実際には出力されない)．

不正解 [3] ～ [12] のいずれかの場合，不正解の種類が "Wrong Answer [5]" のように出力される．
そうでない場合，関数 query の呼び出し回数と，関数 solve の戻り値が "Accepted: 30 true" のように出力される．採点プログラムのサンプルは，実際の採点プログラムと違って不正解 [1], [2] であるか，つまり関数 solve の戻り値が正しいかを判定しないことに注意せよ．

採点プログラムのサンプルは，不正解 [3] ～ [12] のいずれかの不正解の条件が満たされた時点で実行を終了する．実行するプログラムが不正解 [3] ～ [12] のうち，複数の条件を満たした場合，表示される不正解の種類はそれらのうち 1 つのみである．

採点に関する注意

実際の採点プログラムは適応的 (adaptive) ではなく，やりとりの初めから固定された答えを持つ．

制約

2 \leqq N \leqq 500．
1 \leqq M \leqq 1\,000．
0 \leqq A_i \leqq N - 1 (0 \leqq i \leqq M - 1)．
0 \leqq B_i \leqq N - 1 (0 \leqq i \leqq M - 1)．
A_i \neq B_i (0 \leqq i \leqq M - 1)．
(A_i, B_i) \neq (A_j, B_j) かつ (A_i, B_i) \neq (B_j, A_j) (0 \leqq i < j \leqq M - 1)．
N, M, A_i, B_i は整数である (0 \leqq i \leqq M - 1)．

小課題

(4 点) N = 2．
(16 点) N \leqq 100，M = N - 1，B_i = A_{i+1} (0 \leqq i \leqq N - 3)，N 個の値 A_0, A_1, \ldots ,A_{N-2}, B_{N-2} はすべて異なる．
(21 点) M = N - 1，B_i = A_{i+1} (0 \leqq i \leqq N - 3)，N 個の値 A_0, A_1, \ldots ,A_{N-2}, B_{N-2} はすべて異なる．
(24 点) N \leqq 100，A_i \neq A_j (0 \leqq i < j \leqq M - 1)．
(14 点) A_i \neq A_j (0 \leqq i < j \leqq M - 1)．
(11 点) N \leqq 100．
(10 点) 追加の制約はない．

やりとりの例

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

入力例 1

1 回目の \texttt{query} の呼び出しにおける 2 回の電圧の設定と，電流が流れる電気抵抗は以下の通りである．

1 回目は節点 0, 1 を「低電圧」に，節点 2, 3, 4 を「高電圧」に設定する．このとき，電気抵抗 1, 5 に電流が流れる．
2 回目は節点 3, 4 を「低電圧」に，節点 0, 1, 2 を「高電圧」に設定する．このとき，電気抵抗 2 に電流が流れる．

1 回目の電圧の設定の方が電流が流れる電気抵抗の本数が多いため，戻り値は -1 である．

この入力例は小課題 6, 7 の制約を満たす．

コンテストサイトからダウンロードできるファイルのうち，sample-01-in.txt は入力例 1 に対応する．また，sample-02-in.txt は小課題 2, 3, 4, 5, 6, 7 の制約を満たし，sample-03-in.txt は小課題 4, 5, 6, 7 の制約を満たす．