No.3016 ハチマキおじさん
タグ : / 解いたユーザー数 130
作問者 :
のらら
/ テスター :
高橋ゆに
👑 
binap
DeltaStruct
Apollo@Kuro
Yama.can
こめだわら
あじゃじゃ
eom2357
問題文
ハチマキおじさんはAIとyuki(coder)だけが友達です。お腹を空かせた子どもを見つけると自分のハチマキを分けてあげます。
ハチマキおじさんは長さがそれぞれ $A_1, A_2, ... , A_N$ である $N$ 本のハチマキを持っており、 $N-1$ 人の子どもにハチマキを $1$ 本ずつ分けてあげます。
子どもにはそれぞれ好きなハチマキの長さがあり、$j$ 番目の子どもは $B_j$ 以外の長さのハチマキをもらうと不満に感じます。
具体的には $i$ 番目のハチマキを $j$ 番目の子どもに分けてあげたとき、 $|A_i-B_j|$ の不満度が発生します。
適切なハチマキをそれぞれの子どもに分けてあげることで不満度の合計を最小化したとき、 ハチマキおじさんの手元に残る可能性のあるハチマキ $1$ 本の長さの種類数と具体的な長さを昇順ですべて求めてください。
制約
- $2 \leq N \leq 2×10^5$
- $1 \leq A_i, B_i \leq N$
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1\ A_2\ ...\ A_{N-1}\ A_N$
$B_1\ B_2\ ...\ B_{N-1}$
出力
$1$ 行目にはハチマキおじさんの手元に残る可能性のあるハチマキの長さの種類数 $T$ を、$2$ 行目にはその具体的なハチマキの長さ $L$ を昇順で並べた $T$ 項の数列 $L_1\ L_2\ ...\ L_T$ を出力せよ。
サンプル
サンプル1
入力
3 1 2 3 1 1
出力
1 3
長さ $3$ のハチマキのみ手元に残る可能性があります。
$1$ 番目のハチマキを $1$ 番目の子どもに、 $2$ 番目のハチマキを $2$ 番目の子どもに分けてあげることにすると、 不満度の合計は最小の $|1-1|+|2-1|=1$ となります。
これ以外の長さのハチマキを手元に残して不満度の合計が $1$ となる配り方はありません。
サンプル2
入力
5 4 1 5 1 3 5 2 1 5
出力
2 1 3
長さ $1$ と $3$ のハチマキが手元に残る可能性があります。
長さ $1$ のハチマキを手元に残す場合、 $1$ 番目の子どもから順に $3,5,4,1$ 番目のハチマキを分けてあげると不満度の合計は最小の $2$ となります。
長さ $3$ のハチマキを手元に残す場合も、 $1$ 番目の子どもから順に $3,4,2,1$ 番目のハチマキを分けてあげることで不満度の合計は $2$ となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。