問題一覧 > 通常問題

No.490 yuki Sort

レベル : / AI推定難易度 : 167 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 348
作問者 : square1001 / テスター : e869120
お気に入りにしたユーザー ProblemId : 1398 / 自分の提出
問題文最終更新日: 2026-06-25 05:09:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 158 (順位表) の他の問題:

Problem Statement

Sorting means rearranging a sequence into an appropriate order.
In particular, ascending sort means rearranging a sequence into ascending order.

yuki received a sequence $a_0, a_1,\dots, a_{n-1}$ as a birthday present.
Since he loves sorting, he sorted the sequence $a$ using various sorting methods.
After sorting the sequence $a$ with about 30 kinds of algorithms, yuki decided to try creating an algorithm of his own!

So he came up with the following method called "yuki sort".


  1. For each $i$ ($0 < i < 2n - 3$), in increasing order of $i$, perform step 2.
  2. For every pair of integers $(p, q)$ satisfying $p+q=i$ $(0 \le p < q \le n - 1)$, if $a_p > a_q$, swap $a_p$ and $a_q$.

yuki did not know whether this sorting method is correct, so he decided to ask you, his friend and a competitive programmer, to investigate it.
Given an integer $n$ and a sequence $a_0, a_1,\dots, a_{n-1}$, find the sequence after applying yuki sort.
(Note that the result is uniquely determined regardless of the order of the swaps.)

Input

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

The first line contains an integer $n$ $(2 \le n \le 2000)$.
The second line contains the elements of the sequence $a_0, a_1, a_2,\dots,a_{n-1}$ $(1 \le a_i \le 10^9)$.

Output

Output the sequence $a$ after applying yuki sort, separated by spaces.
Do not forget the newline at the end.

Sample

Sample 1
Input
15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
Output
1 1 2 3 3 4 5 5 5 6 7 8 9 9 9

When $a=\{3,1,4,1,5,9,2,6,5,3,5,8,9,7,9\}$, yuki sort sorts it correctly.

Sample 2
Input
5
1 2 3 4 5
Output
1 2 3 4 5

The sequence is already sorted.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。