注意

この問題はアドベコン用の問題です。

正当な出力をしてACすることができたら★1.5相当の点数が与えられます。

スコア問題としての順位は「スコア順」タブをご覧ください。

実行制限時間について

この問題の実行制限時間は $1224\text{ms}$ であることに注意してください。

比較的遅い言語でもACすることは可能ですが、より良いスコアを目指す場合は高速な言語を使うことをおすすめします。

元ネタ

ABC115 C - Christmas Eve

問題文

$N$ 個の「木の先端」、$2N$ 個の「木の中央」、$N$ 個の「木の幹」があります。以降、これらをまとめてパーツと呼びます。

• $i$ 個目の「木の先端」は幅、高さがそれぞれ $a_i,b_i$ です。
• $j$ 個目の「木の中央」は幅、高さがそれぞれ $c_j,d_j$ です。
• $k$ 個目の「木の幹」は幅、高さがそれぞれ $e_k,f_k$ です。

クリスマスツリーを $1$ つ作るには、「木の先端」を $1$ つ、「木の中央」を $2$ つ、「木の幹」を $1$ つ、以下の条件をすべて満たすように選ぶ必要があります。

• 「木の幹」の幅は、選んだ他のパーツの幅よりも小さい
• 「木の先端」の幅は、選んだどちらの「木の中央」の幅よりも小さい

クリスマスツリーの高さは、選んだパーツの高さの合計です。

はるく君は、パーツを組み合わせて $K$ 個のクリスマスツリーを作ろうとしています。ただし、複数のクリスマスツリーに同じパーツを使うことはできません。

はるく君は、作ったクリスマスツリーの高さができる限り近くなるようにしたいです。

より正確には、作ったクリスマスツリーの中で最も高いものの高さを $H_{max}$ 、最も低いものの高さを $H_{min}$ として、$H_{max}-H_{min}$ をできる限り小さくしたいです。

はるく君のために、 $H_{max}-H_{min}$ が小さいクリスマスツリーの作り方を教えてあげてください。

入力

$N\ K$
$a_1,a_2,\dots,a_N$
$b_1,b_2,\dots,b_N$
$c_1,c_2,\dots,c_{2N}$
$d_1,d_2,\dots,d_{2N}$
$e_1,e_2,\dots,e_N$
$f_1,f_2,\dots,f_N$

• $N=500$
• $300\leq K\leq 400$
• $1\leq a_i,b_i,c_i,d_i,e_i,f_i\leq 10000$
• 入力はすべて整数
• 問題文中の条件を満たすように $K$ 個のクリスマスツリーを作れる

出力

$K$ 行出力してください。

$i$ 行目には、$i$ 番目のクリスマスツリーに $u_i$ 番目の「木の先端」、$v_i$ 番目と $w_i$ 番目の「木の中央」、$x_i$ 番目の「木の幹」を使うとき、以下のように出力してください。

$u_i\ v_i\ w_i\ x_i$

このとき、以下の条件をすべて満たす必要があります。

• $1\leq u_i,x_i\leq N$
• $1\leq v_i,w_i\leq 2N$
• $u_i\ne u_j,v_i\ne v_j,w_i\ne w_j,x_i\ne x_j(i\ne j)$
• $v_i\ne w_j$
• $e_{x_i}< a_{u_i}$
• $e_{x_i}< c_{v_i}$
• $e_{x_i}< c_{w_i}$
• $a_{u_i}< c_{v_i}$
• $a_{u_i}< c_{w_i}$

得点

出力が問題文の条件を満たしていない場合、WAと判定されます。そうでなく、プログラムが時間内に正常終了していればACと判定されます。

テストケースの得点は、 $40000-(H_{max}-H_{min})$ です。

提出コードはのスコアは、125個のテストケースすべての得点の合計です。コンテスト後のシステムテストは行われません。

入力生成方法

この項目を読まなくても問題の理解に支障はありません。

平均 $μ$ 、標準偏差 $σ$ の正規分布にしたがって乱数を生成する関数を $\text{normal}(μ,σ)$ 、 $a$ 以上 $b$ 以下の整数を一様ランダムに生成する関数を $\text{rand}(a,b)$ と表します。

1. $N=500,$ $K=\text{rand}(300,400)$ とします。

2. $1\le i\le K,1\le j\le4$ に対して
   $w_{i,j}=\max(1,\min(10000,\lfloor \text{normal}(5000,1600) \rfloor))$ とします。
   ただし、 $w_i$ に同じ値が複数回出現するような $i$ が存在すれば $w_i$ の各要素の生成はやり直され、それはこのような $i$ が存在しなくなるまで続けられます。

3. 各 $i$ について $w_i$ の要素を昇順に並び替えます。

4. $1\le i\le K$ について

   • $a_i=w_{i,2}$
   • $c_{i}=w_{i,3}$
   • $c_{i+N}=w_{i,4}$
   • $e_i=w_{i,1}$
   とします。

5. $K+1\le i\le N$ について

   • $a_i=\max(1,\min(10000,\lfloor \text{normal}(5000,1600) \rfloor))$
   • $c_{i}=\max(1,\min(10000,\lfloor \text{normal}(5000,1600) \rfloor))$
   • $c_{i+N}=\max(1,\min(10000,\lfloor \text{normal}(5000,1600) \rfloor))$
   • $e_i=\max(1,\min(10000,\lfloor \text{normal}(5000,1600) \rfloor))$
   とします。

6. $a,c,e$ をランダムに並び替えます。

7. $1\le i\le N$ について

   • $b_i=\max(1,\min(1000,\lfloor \text{normal}(a_i,500)\rfloor))$
   • $d_i=\max(1,\min(1000,\lfloor \text{normal}(d_i,500)\rfloor))$
   • $d_{i+N}=\max(1,\min(1000,\lfloor \text{normal}(d_{i+N},500)\rfloor))$
   • $f_i=\max(1,\min(1000,\lfloor \text{normal}(f_i,500)\rfloor))$
   とします。

import random

def high(wide):
    return max(1,min(10000,int(random.gauss(wide,500))))
N=500
K=random.randint(300,400)
a=[]
b=[]
c=[]
d=[]
e=[]
f=[]
for i in range(K):
    wide=[max(1,min(10000,int(random.gauss(5000,1600)))) for i in range(4)]
    while len(set(wide))!=4:
        wide=[max(1,min(10000,int(random.gauss(5000,1600)))) for i in range(4)]
    wide.sort()
    e.append(wide[0])
    c.append(wide[3])
    c.append(wide[2])
    a.append(wide[1])
for i in range(N-K):
    e.append(max(1,min(10000,int(random.gauss(5000,1600)))))
    c.append(max(1,min(10000,int(random.gauss(5000,1600)))))
    c.append(max(1,min(10000,int(random.gauss(5000,1600)))))
    a.append(max(1,min(10000,int(random.gauss(5000,1600)))))
random.shuffle(a)
random.shuffle(c)
random.shuffle(e)
for i in range(N):
    b.append(high(a[i]))
    f.append(high(e[i]))
    d.append(high(c[i*2]))
    d.append(high(c[i*2+1]))
print(N,K)
print(*a)
print(*b)
print(*c)
print(*d)
print(*e)
print(*f)

サンプル

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

1 2 5 1
2 3 1 2