TopCoder

Thumb vi punching
Caido
$\text{W}ai\text{M}ai\sim$

User's AC Ratio

97.8% (87/89)

Submission's AC Ratio

53.6% (112/209)

Description

布朗博士搭乘著時光機器回到了原始人出現的年代,他打算教導原始人現代的資訊技術。首先,布朗博士教原始人們數字的二進位表示法,他由小而大列下了幾個數字:
$000, 001, 010, 011, 100, 101, 110, 111$
剛列完,原始人的首領就糾正他,說下面的列法才是正確由小到大的順序:
$000, 001, 010, 100, 011, 101, 110, 111$
爭吵了半天,布朗博士才發現,原來原始人在計數時是用石頭在牆上刻劃一道道的痕跡,每道痕跡 就算計數一次,因此在二進位的表示法下,$1$ 的次數愈多,在原始人心中認定的數值愈大。
請你寫一支程式幫助布朗博士,將 $n$ 個十進位表示的數字依原始人認定的順序(即二進位表示法中$1$ 的個數)由小而大排序;倘若兩數字的二進位表示中 $1$ 的個數相同,則視為相同,依輸入時的順序輸出。

Input Format

$n$
$a_1\ a_2\ \dots\ a_n$

  • $n$:輸入數字的個數
  • $a_i$:第 $i$ 個需要排序的數字,以十進位整數表示

Output Format

$b_1\ b_2\ \dots\ b_n$

  • $b_i$:排序完後,順序第 $i$ 的數字,以十進位整數表示

Sample Input

Sample Input 1
5
3 2 4 1 5

Sample Input 2
3
10 11 12

Sample Output

Sample Output 1
2 4 1 3 5

Sample Output 2
10 12 11

Hints

測資限制

  • $1 \leq n \leq 10^ 3$。
  • $1 \leq a_i \leq 1024 = 2^ {10}$。($i\in \{1,2,\dots,n\}$)
  • 輸入給的 $n$ 個數字皆相異,也就是對整數 $1\leq i<j\leq n$ 滿足 $a_i\neq a_j$。
  • 上述所有變數均為整數。

評分說明
本題共有二組子任務,條件限制如下所示。每一子任務可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

  1. (40%) $a_i \leq 7$。
  2. (60%) 無額外限制。

Problem Source

2021 TOI 入營考 pA
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~9 $a_i \leq 7$。 40
2 0~29 無額外限制。 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 1 2
4 1000 524288 65536 1 2
5 1000 524288 65536 1 2
6 1000 524288 65536 1 2
7 1000 524288 65536 1 2
8 1000 524288 65536 1 2
9 1000 524288 65536 1 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
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2