No.909 たぴの配置

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 161
作問者 : TaprisちゃんTaprisちゃん / テスター : たぴちゃんたぴちゃん
5 ProblemId : 2988 / 出題時の順位表

問題文

$N + 2$ 匹のたぴがいて, $0$ から $N + 1$ まで番号づけされています。

すべてのたぴを数直線上の整数座標に配置します。複数のたぴが同じ座標に配置されていても構いません。

ただしたぴ $i(1 \leq i \leq N)$ についてつぎの条件を満たす必要があります。

  • たぴ $i$ からたぴ $0$ までの距離が $X_i$ 以下である
  • たぴ $i$ からたぴ $N + 1$ までの距離が $Y_i$ 以下である

たぴ $0$ とたぴ $N + 1$ は仲が悪いです。そこで, たぴ $0$ からたぴ $N + 1$ までの距離の最大値と, そのときのたぴの配置の例を求めてください。

入力

$N$
$X_1$ $X_2$ $\cdots$ $X_N$
$Y_1$ $Y_2$ $\cdots$ $Y_N$
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq X_i, Y_i \leq 10^6$
  • 入力はすべて整数

出力

出力は $N + 3$ 行からなります。

$1$ 行目には, たぴ $0$ からたぴ $N + 1$ までの距離の最大値を出力してください。

つづく $N + 2$ 行に渡って, $N + 2$ 匹のたぴの座標をたぴ $0$ から順に各行に出力してください。

たぴの座標はすべて $0$ 以上 $10^{18}$ 以下の整数である必要があります。

条件を満たす配置が複数考えられる場合がありますが, どれを出力しても構いません。

サンプル

サンプル1
入力
2
1 10
2 1
出力
3
0
1
2
3

たぴ $0$ からたぴ $3$ までの距離の最大値は $3$ です。

たぴ $0$ からたぴ $3$ をそれぞれ座標 $0, 1, 2, 3$ におくと

  • たぴ $1$ からたぴ $0$ までの距離は $1$
  • たぴ $1$ からたぴ $3$ までの距離は $2$
  • たぴ $2$ からたぴ $0$ までの距離は $2$
  • たぴ $2$ からたぴ $3$ までの距離は $1$

となり, すべての条件を満たしています。

サンプル2
入力
3
0 0 0
0 0 0
出力
0
3
3
3
3
3

たぴ $0$ からたぴ $4$ までの距離の最大値は $0$ です。

全てのたぴを同じ座標に配置する必要があります。

サンプル3
入力
3
50 20 1
40 30 1
出力
2
2
35
15
1
0

たぴ $0$ からたぴ $4$ までの距離の最大値は $2$ です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。