No.322 Geometry Dash

レベル : / 実行時間制限 : 1ケース 2秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 44
作問者 : ichyo

6

問題文

Geometry Dash は $N$ 個の難所からなるステージをクリアするゲームです. このゲームの製作者であるあなたは,必要なクリア時間が最大になるように $N$ 個の難所の順番を決めることにしました. このゲームのクリア時間は以下のように計算されます.

$N$ 個の難所には,それぞれ通過に必要な時間 $T_i$ と難易度 $D_i$ ( $i = 1, 2, \dots, N$ ) が決まっています.また,$N$ 個の難所はあらかじめ決められた順番通りに辿る必要があります. $i$ 番目の難所は, 到達する直前の到達回数が $D_i$ 回以上のときに通過することができます.ただし,到達回数はそれぞれの難所について独立に数えるものとします. 到達回数が $D_i$ 回未満のときは,到達してから $T_i / 2$ 時間経過した後に,開始地点に戻され,ふたたび $1$ つ目の難所から辿りはじめます. クリア時間は,$N$ 個の難所を決められた順番ですべて辿るために必要な時間の合計です.ただし,難所の間を移動する時間や開始地点に戻る時間は無視してください.

例えば, $3$ 個の難所が前から順番に $T = \{2, 6, 4\}$, $D = \{1, 2, 1\}$ となるように並べられていた場合, クリア時間は $33$ であり,以下の図のように計算されます.

クリア時間を最大化するような $N$ 個の難所の順番を計算して出力してください.複数の候補がある場合はどれでも出力してかまいません.

入力

$N$
$T_1$ $T_2$ ... $T_N$
$D_1$ $D_2$ ... $D_N$
  • $2 \le N \le 10^5$
  • $1 \le T_i \le 10^4$
  • $1 \le D_i \le 10^4$

出力

$N$ 個の整数 $X_i$ を空白区切りで一行で出力してください. $i$ 番目の整数 $X_i$ は,入力における $X_i$ 番目の難所が $i$ 番目に並び替えられることを表します.

サンプル

サンプル1
入力
3
2 6 4
1 2 1
出力
3 2 1

入力で与えられた順番の逆に並び替えたとき,クリア時間は最大になります.

サンプル2
入力
5
1 1 1 1 1
1 1 1 1 1
出力
1 2 3 4 5

候補が複数ある場合はどれを出力しても構いません.

サンプル3
入力
10
1 1 1 1 1 1 1 1 1 1
10 16 253 190 469 12 29 57 797 584
出力
1 6 2 7 8 4 3 5 10 9

サンプル4
入力
7
2 7 3 6 8 1 1
6 1 67 56 56 1 21
出力
2 6 1 5 4 7 3

提出ページヘ