結果
問題 |
No.14 最小公倍数ソート
|
ユーザー |
👑 |
提出日時 | 2022-09-27 21:25:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 343 ms / 5,000 ms |
コード長 | 2,196 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 89,344 KB |
最終ジャッジ日時 | 2024-12-22 17:10:59 |
合計ジャッジ時間 | 6,805 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
import heapq class Heapq: def __init__(self, lst = [], reverse = False): if reverse: self.pm = -1 self.hq = [-l for l in lst] else: self.pm = 1 self.hq = lst[:] heapq.heapify(self.hq) self.tot = sum(lst) self.cnt = {} for l in lst: self.cnt[l * self.pm] = self.cnt.get(l * self.pm, 0) + 1 self.length = len(lst) def __bool__(self): return self.length > 0 def __len__(self): return self.length def __getitem__(self, i): if i == 0: return self.top() else: assert False def push(self, x): self.length += 1 self.cnt[x * self.pm] = self.cnt.get(x * self.pm, 0) + 1 heapq.heappush(self.hq, x * self.pm) self.tot += x def pop(self): if self.length == 0: return None self.length -= 1 ret = heapq.heappop(self.hq) self.tot -= self.pm * ret self.cnt[ret] -= 1 self.delete() return self.pm * ret def top(self): if self.hq: return self.pm * self.hq[0] else: return None def remove(self, x): if self.cnt.get(x * self.pm, 0) == 0: return False self.cnt[x * self.pm] -= 1 self.length -= 1 self.tot -= x self.delete() return True def delete(self): while self.hq and self.cnt.get(self.hq[0], 0) == 0: heapq.heappop(self.hq) n = int(input()) A = list(map(int, input().split())) ma = 10000 div = [[] for _ in range(ma + 1)] for i in range(1, ma + 1): for j in range(i, ma + 1, i): div[j].append(i) hq = [Heapq() for _ in range(ma + 1)] for a in A[1:]: for d in div[a]: hq[d].push(a) a = A[0] ans = [a] for _ in range(n - 1): mi = 1 << 30 x = -1 for d in div[a]: if not hq[d]: continue b = hq[d].top() y = a * b // d if y < mi: mi = y x = b a = x ans.append(a) for d in div[a]: hq[d].remove(a) print(*ans)