結果
問題 | No.14 最小公倍数ソート |
ユーザー | maspy |
提出日時 | 2020-03-25 00:43:52 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 251 ms / 5,000 ms |
コード長 | 1,839 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 10,984 KB |
実行使用メモリ | 18,312 KB |
最終ジャッジ日時 | 2023-08-30 09:08:30 |
合計ジャッジ時間 | 5,144 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 64 ms
14,808 KB |
testcase_01 | AC | 64 ms
14,780 KB |
testcase_02 | AC | 67 ms
14,656 KB |
testcase_03 | AC | 88 ms
15,208 KB |
testcase_04 | AC | 249 ms
18,128 KB |
testcase_05 | AC | 165 ms
16,888 KB |
testcase_06 | AC | 174 ms
17,248 KB |
testcase_07 | AC | 194 ms
17,484 KB |
testcase_08 | AC | 217 ms
17,720 KB |
testcase_09 | AC | 237 ms
18,076 KB |
testcase_10 | AC | 242 ms
18,008 KB |
testcase_11 | AC | 251 ms
18,312 KB |
testcase_12 | AC | 237 ms
18,284 KB |
testcase_13 | AC | 240 ms
18,176 KB |
testcase_14 | AC | 234 ms
18,140 KB |
testcase_15 | AC | 241 ms
18,180 KB |
testcase_16 | AC | 177 ms
17,284 KB |
testcase_17 | AC | 155 ms
16,924 KB |
testcase_18 | AC | 126 ms
16,232 KB |
testcase_19 | AC | 209 ms
17,584 KB |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from heapq import heapify, heappop from collections import defaultdict N, *A = map(int, read().split()) class RemovableHeap(): def __init__(self, data): self.n_elem = len(data) self.data = data heapify(self.data) self.counter = defaultdict(int) for x in data: self.counter[x] += 1 def top(self): while True: x = self.data[0] if not self.counter[x]: heappop(self.data) continue return x def push(self, x): self.counter[x] += 1 heappush(self.data, x) self.n_elem += 1 def pop(self): while True: x = heappop(self.data) if self.counter[x]: self.counter[x] -= 1 self.n_elem -= 1 return x def remove(self, x): self.counter[x] -= 1 self.n_elem -= 1 def empty(self): return self.n_elem == 0 U = 10 ** 4 div = [[] for _ in range(U + 1)] for d in range(1, U + 1): for i in range(d, U + 1, d): div[i].append(d) INF = 10 ** 9 multiples = [[INF] for _ in range(U + 1)] for x in A[1:]: for d in div[x]: multiples[d].append(x) for i in range(1, U + 1): multiples[i] = RemovableHeap(multiples[i]) answer = [A[0]] n = A[0] for _ in range(N - 1): best_lcm = INF best_x = 0 for d in div[n]: x = multiples[d].top() lcm = n * x // d if best_lcm > lcm: best_lcm = lcm best_x = x n = best_x answer.append(n) for d in div[n]: multiples[d].remove(n) print(*answer) # %% # import numpy as np # from numba import njit # %%