結果
問題 |
No.14 最小公倍数ソート
|
ユーザー |
|
提出日時 | 2023-03-01 10:01:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 123 ms / 5,000 ms |
コード長 | 856 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 81,180 KB |
最終ジャッジ日時 | 2024-09-16 09:43:46 |
合計ジャッジ時間 | 3,171 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
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)