結果
問題 | No.14 最小公倍数ソート |
ユーザー | H3PO4 |
提出日時 | 2023-03-01 10:01:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 142 ms / 5,000 ms |
コード長 | 856 bytes |
コンパイル時間 | 371 ms |
コンパイル使用メモリ | 87,228 KB |
実行使用メモリ | 82,608 KB |
最終ジャッジ日時 | 2023-10-14 15:13:02 |
合計ジャッジ時間 | 4,101 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 89 ms
77,900 KB |
testcase_01 | AC | 90 ms
77,568 KB |
testcase_02 | AC | 93 ms
77,736 KB |
testcase_03 | AC | 112 ms
78,056 KB |
testcase_04 | AC | 136 ms
82,376 KB |
testcase_05 | AC | 141 ms
81,484 KB |
testcase_06 | AC | 137 ms
81,616 KB |
testcase_07 | AC | 132 ms
81,608 KB |
testcase_08 | AC | 137 ms
82,028 KB |
testcase_09 | AC | 142 ms
82,608 KB |
testcase_10 | AC | 141 ms
82,016 KB |
testcase_11 | AC | 140 ms
82,224 KB |
testcase_12 | AC | 140 ms
82,124 KB |
testcase_13 | AC | 133 ms
82,396 KB |
testcase_14 | AC | 135 ms
82,196 KB |
testcase_15 | AC | 138 ms
82,240 KB |
testcase_16 | AC | 136 ms
81,668 KB |
testcase_17 | AC | 135 ms
81,544 KB |
testcase_18 | AC | 135 ms
81,188 KB |
testcase_19 | AC | 130 ms
81,704 KB |
ソースコード
from collections import Counter N = int(input()) A = tuple(map(int, input().split())) MAX = 10000 divisors = [[] for _ in range(MAX + 1)] for i in range(1, MAX + 1): for j in range(i, MAX + 1, i): divisors[j].append(i) ct = Counter(A) multiple = [[] for _ in range(MAX + 1)] for a in sorted(ct.keys(), reverse=True): for x in divisors[a]: multiple[x].append(a) cur = A[0] ans = [] while len(ans) < N: ans.append(cur) ct[cur] -= 1 next_cur = 0 tmp_lcm_min = MAX ** 2 for x in divisors[cur]: while multiple[x] and not ct[multiple[x][-1]]: multiple[x].pop() if multiple[x]: tmp_next_cur = multiple[x][-1] if tmp_lcm_min > tmp_next_cur // x: tmp_lcm_min = tmp_next_cur // x next_cur = tmp_next_cur cur = next_cur print(*ans)