735 . 分治排序

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

asuka
酸欠少女

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

93.8% (15/16)

Tags

apcsc apcsc-dc

Description

請你實作基於分治法的 $O(N \log N)$ 合併排序法。

本題目的是排序練習，請不要使用 std::sort, std::nth_element 等任何對排序有直接或間接幫助的 STL 函式。

Input Format

輸入第一行是一個正整數 $N$。
第二行有 $N$ 個數字 $a_1, a_2, \dots, a_N$，代表待排序的數字。

輸入保證 $1\le N\le 2\times 10^ 5$，$1\le a_i\le 10^ 9$。

Output Format

輸出一行 $N$ 個以空白分隔的整數，表示將輸入排序好的結果。

Sample Input 1

3
1 4 2

Sample Output 1

1 2 4

Sample Input 2

5
3 4 2 5 4

Sample Output 2

2 3 4 4 5

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
Submit
Back to Top