37. 奇怪的排序题

单点时限: 1.0 sec

内存限制: 256 MB

所有数据在内存中都是以二进制形式存放的,其中有一些位是 1,而另一些位是 0。例如,整数 100 的二进制表示为 1100100,其中 1 的位数是 3;整数 15 的二进制表示为 1111,其中 1 的位数是 4;整数 -15 的 64 位二进制表示为 1111111111111111111111111111111111111111111111111111111111110001,其中 1 的位数是 61。

现在有 $n$ 个整数,要求按照 64 位二进制补码表示中 1 的位数从大到小进行排序。若两个数的二进制表示中 1 的位数相同,则按照数本身值由小到大排序。

输入格式

第 1 行:$n$。

第 2 行:$n$ 个待排序的数 $a_1,a_2,\ldots,a_n$ ($-10^{18} \le a_i \le 10^{18}$),每两个数之间由一个空格分隔。

数据规模约定:共有 $10$ 个数据点。

  • $1,2,3$: $1 \le n \le 100, \ \ 0 \le a_i \le 10^{18}$;
  • $4,5$: $1 \le n \le 100, \ \ -10^{18} \le a_i \le 10^{18}$;
  • $6,7$: $1 \le n \le 10^4, \ \ 0 \le a_i \le 10^{18}$;
  • $8,9$: $1 \le n \le 5 \cdot 10^4, \ \ -10^{18} \le a_i \le 10^{18}$;
  • $10$: $1 \le n \le 5 \cdot 10^5, \ \ 0 \le a_i \le 10^{18}$.

输出格式

在一行中输出排序后的数。

样例

Input
8
100 15 0 30 7 -15 100 -100
Output
-15 -100 15 30 7 100 100 0

78 人解决,153 人已尝试。

102 份提交通过,共有 970 份提交。

5.1 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,8 月前.

最后提交: 1 周,5 天前.

来源: 2017 程序设计基础期末考

题目标签