No.490 yukiソート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 111
作問者 : square1001square1001 / テスター : e869120e869120

2 ProblemId : 1398 / 出題時の順位表

問題文

ソートとは, 数列を適切な順番に並び替えることです。
特に, 昇順ソートとは, 数列を昇順に並び替えることです。

yuki君は誕生日プレゼントに数列 $a_0, a_1,\dots, a_{n-1}$ をもらいました。
彼はソートが大好きなので, いろいろなソートの方法で数列$a$をソートしました。
30種類くらいのアルゴリズムで数列$a$をソートしたyuki君は, 自分でもアルゴリズムを作ってみようと思いました!

そこで, 次の「yukiソート」という方法を考えました。


  1. 各 $i$ ($0 < i < 2n - 3$) に対して、$i$ の小さい順に 2. を行う
  2. $p+q=i$ $(0 \le p < q \le n - 1)$ を満たす整数の組 $(p, q)$ 全てに対して、$a_p > a_q$ ならば $a_p$ と $a_q$ を交換する

yuki君は, このソートの方法が正しいかどうか分からなかったので, yuki君の友達でありかつ競プロerであるあなたに調べてもらうことにしました。
整数 $n$ と 数列 $a_0, a_1,\dots, a_{n-1}$ が与えられるとき, yukiソートした後の数列を求めなさい。
(交換順に関わらず一意の結果になることに注意)

入力

$n$
$a_0$ $a_1$ ... $a_{n-1}$

1行目に整数 $n$ $(2 \le n \le 2000)$ が与えられる。
2行目に数列の要素 $a_0, a_1, a_2,\dots,a_{n-1}$ $(1 \le a_i \le 10^9)$ が与えられる。

出力

yukiソートした後の数列 $a$ を空白区切りで出力しなさい。
最後の改行を忘れないこと。

サンプル

サンプル1
入力
15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力
1 1 2 3 3 4 5 5 5 6 7 8 9 9 9

$a=\{3,1,4,1,5,9,2,6,5,3,5,8,9,7,9\}$ の場合, yukiソートで正しくソートされます。

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

数列はすでにソートされています。

提出ページヘ