Hide

鉄道旅行

電車で移動することになり、どこに座ろうかと考えているグループがいます。 $m$組のペアの人たちは友達で、できるだけ近くに座りたいと思っています。 彼らが座ろうとしている電車の車両には、$N$列の座席があり、$N \times 4$の格子状に配置されていて、各列に$4$席があります。 グループの中には、$4N$人がいます。 それぞれの人には、$1$から$4N$までの番号が振られています。

ユークリッド距離 $L = \sqrt{dx^2 + dy^2}$ だけ離れた席に座っている友達のペアは、グループの幸福度に $1/L^2$ を与えます。 あなたの課題は,グループの幸福度が最大になるように人を配置することです.

入力

入力は$10$個のテストケースで構成されています。

最初の行には数 $T$ ($0 T \le T \le 10$) を含みます。これは、テストケースの番号(サンプルの場合は$0$)を表します。 2行目には、数 $N$$M$$1 \le N \le 25\, 000$, $1 \le M \le 100\, 000$)があり、車内の列の数と友達のペアの数を表します。 以降の$M$行には、2つの整数$a$$b$ ($1 \le a,b \le 4N$, $a \ne b$) があり、$a$$b$が友達だということを表します。

出力

各行に $4$ 個の整数を含む $N$ 行を出力します。 各行には、その行に座っている4人の番号を出力します。 すべての人をどこかに配置しなければなりません。

得点

プログラムは、$10$ 個のテストケースでテストを行います。

投稿に対する得点は、それぞれのテストケースに対する得点の合計となります。

あなたのスコアは、審査員の解答に対して相対的に設定されます。 あなたの解答が審査員の解答よりも優れている場合、テストケースの得点は$10$点以上になることがあります。 しかし、合計得点は$100$点に制限されます。

サンプル問題の得点は $0$ 点です。

サンプルの説明

サンプル問題では、$8$人を $2 \times 4$ のグリッドに配置します。 解答は、$1$$4$ (彼らは距離 $\sqrt3$) 以外の友達の距離を最適化しています。 幸福度の合計は、$4 \cdot 1/1 + 1/3 \approx 4.33$となります。

よりよい解として、すべての友達の距離を$1$にすることが可能です。

テストケース

友達の関係グラフは下記の記述で$G$と呼びます。 $10$個のテストケースを説明します。

Test case

Bounds

Description of test case

$1$

$N = 10$, $M = 100$

$G$ の全ての頂点はランダムに生成されます。

$2$

$N = 100$, $M = 500$

$G$ の全ての頂点はランダムに生成されます。

$3$

$N = 100$, $M = 8\, 000$

$G$ の全ての頂点はランダムに生成されます。

$4$

$N = 8\, 000$, $M \le 45\, 000$

$G$ はサイズ$1$ - $5$ の友達のグループ (全員が友達) で構成されます。

$5$

$N = 2\, 500$, $M = 8\, 000$

$G$ には循環がありません。$G$内の最大距離は$2$です。

$6$

$N = 2\, 500$, $M = 9\, 800$

$G$ には循環がありません。$G$内の最大距離は$2$です。

$7$

$N = 2\, 500$, $M = 9\, 999$

$G$ には循環がありません。

$8$

$N = 25\, 000$, $M = 99\, 999$

$G$ には循環がありません。

$9$

$N = 10\, 000$, $M = 100\, 000$

$G$ の全ての頂点はランダムに生成されます。

$10$

$N = 25\, 000$, $M = 100\, 000$

$G$ の全ての頂点はランダムに生成されます。

「ランダム」は、次の意味です。 連続一様分布.

サンプル入力 1 サンプル出力 1
0
2 5
5 7
8 7
1 2
2 3
1 4
6 5 7 8
1 2 3 4
CPU Time limit 6 seconds
Memory limit 1024 MB
Difficulty 4.6 - 9.3hard
Statistics Show
Languages English, 日本語, Svenska
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in