メモ

スコアとしての順位はこちらをご覧ください https://yukicoder.me/problems/no/5004/score

この問題は、Advent Calendar Contest 2021 1日目の問題です。
難易度は、Advent Calendar Contest 用に付けられたものです。正当な出力を行うことが出来ればコンテストで得点を獲得できます。

スコア問題であるため、最後の提出から5分間は次の提出を行うことができません。

この問題に対しての、(Writerが想定している)コンテスト中の言及ルールは以下です。

• 解法に直接かかわらない部分(ローカルテストの方法等)について、議論や相談を認めます。
• ビジュアライザを有志で作成し公開するなどしても構いません。
• さらに、自身の解法を直接言及することも、コードを共有することも認めます。
• ただし、そのことによって他の方が解を改良した場合、その得点は改良したコードの提出者のものとなります。

問題文

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

あなたは、とあるネットゲームのサーバーエンジニアです。
あなたの任務は、出現するプレイヤーを、なるべく実力の近いプレイヤー同士が同じ部屋になるように、かつなるべく速やかに部屋分けするプログラムを書くことです。

最初に、 $2$ 整数 $T,R$ が以下の形式で与えられます。

$T$ $R$

$N$ $S_1$ $S_2$ $\dots$ $S_N$

$M$
$U_1$ $V_1$
$U_2$ $V_2$
$\dots$
$U_M$ $V_M$

採点方法

部屋を構成するプレイヤーのうち、最もスキル値の大きいプレイヤーのスキル値を $S_M$ 、最もスキル値の小さいプレイヤーのスキル値を $S_m$ とします。
また、 $E$ を以下のように定義します。
$E=\sum_{i,j}$ ( $i$ が $x$ ティック目に出現し、 $(i,j)$ が $y$ ティック目に同じ部屋になった場合、 $y-x$ )
但し、 $\sum_{i,j}$ で同じ部屋にいる全ての相異なるプレイヤーの組 $(i,j)$ $(i \neq j)$ についての総和を表します。
このとき、各部屋の価値を以下のように定義します。

• 部屋に $1$ 人いる場合、部屋の価値は $0$
• 部屋に $2$ 人いる場合、部屋の価値は $\max(1 \times (200-(S_M-S_m)^2) - E,0)$
• 部屋に $3$ 人いる場合、部屋の価値は $\max(3 \times (200-(S_M-S_m)^2) - E,0)$
• 部屋に $4$ 人いる場合、部屋の価値は $\max(6 \times (200-(S_M-S_m)^2) - E,0)$

入力生成方法

• 採点に用いられるテストケースの数は $100$
• $T=3600$ で固定
• $R=4$ で固定
• $N$ の総和は $5400$ で固定
• 全ての $S_i$ に対し、 $0 \le S_i \le 100$

配布物等

こちらから配布物(zip)を入手してください。
githubからも同一の内容が入手可能です。
この配布物を解答に用いたり、この配布物を他言語に翻訳したものを再配布しても構いません。
ローカルテストの際の注意:
この問題では、入力ファイルの内容がそのまま、インタラクションにより順を追ってコードに与えられることで採点が行われます。
そのため、ローカルテストの際は、ジャッジによるインタラクションは不要です。
適切なタイミングで適切な情報を受け取る実装にしてコードを実行して出力ファイルを生成し、それを採点プログラムに与えて採点結果を得てください。

サンプル

6 4
1 5
2 4 7
2 50 4
3 4 4 4
2 0 51
2 100 100

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