結果
問題 | No.14 最小公倍数ソート |
ユーザー | anta |
提出日時 | 2014-10-31 03:18:30 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 687 ms / 5,000 ms |
コード長 | 2,543 bytes |
コンパイル時間 | 85 ms |
コンパイル使用メモリ | 7,040 KB |
実行使用メモリ | 47,864 KB |
最終ジャッジ日時 | 2024-06-09 18:06:24 |
合計ジャッジ時間 | 9,301 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 19 ms
8,192 KB |
testcase_01 | AC | 18 ms
8,192 KB |
testcase_02 | AC | 19 ms
8,064 KB |
testcase_03 | AC | 66 ms
12,032 KB |
testcase_04 | AC | 653 ms
47,864 KB |
testcase_05 | AC | 345 ms
30,720 KB |
testcase_06 | AC | 414 ms
32,896 KB |
testcase_07 | AC | 458 ms
36,480 KB |
testcase_08 | AC | 531 ms
40,832 KB |
testcase_09 | AC | 609 ms
45,672 KB |
testcase_10 | AC | 607 ms
45,156 KB |
testcase_11 | AC | 641 ms
46,824 KB |
testcase_12 | AC | 625 ms
46,448 KB |
testcase_13 | AC | 651 ms
47,088 KB |
testcase_14 | AC | 627 ms
46,316 KB |
testcase_15 | AC | 687 ms
47,604 KB |
testcase_16 | AC | 380 ms
32,256 KB |
testcase_17 | AC | 320 ms
28,160 KB |
testcase_18 | AC | 197 ms
21,504 KB |
testcase_19 | AC | 495 ms
39,296 KB |
ソースコード
# <http://yukicoder.me/submissions/1252>をPythonに移植 # Pythonには慣れてないのでそのまま移植した感なコードになってるかと… # ちなみに↑の"シンプルに…"のところは嘘だった。正しくはO(N X^\epsilon + X^{1+\epsilon})とかそんなん(まだ自信ない) # ちなみに数xの約数の数は"最悪"O(x^\epsilon)で抑えられる。"divisor bound"と言うらしい。平均はΘ(log x)。 # Xの値をテスト用から変えるの忘れてた… import random def getSmallestPrimeFactors(n): res = [0] * (n+1) res[1] = 1 for i in xrange(2, n+1): if res[i] == 0: res[i] = i for j in xrange(i * i, n+1, i): if res[j] == 0: res[j] = i return res def primeFactors(x, smallestPrimeFactor): res = [] while x != 1: p, k = smallestPrimeFactor[x], 1 x //= p while x % p == 0: x //= p k += 1 res.append((p, k)) return res def getDivisors(x, smallestPrimeFactor): fs = primeFactors(x, smallestPrimeFactor) res = [1] for p, k in fs: for x in res[:]: for _ in xrange(k): x *= p res.append(x) return res class Node: def __init__(self, i): self.i = i self.prev, self.next = None, None def insertToList(head, t): t.next = head if head: head.prev = t return t def removeFromList(head, t): if t.prev: t.prev.next = t.next if t.next: t.next.prev = t.prev if head is t: head = t.next t.prev, t.next = None, None return head N = int(raw_input()) a = map(int, raw_input().split(" ")) X = 10000 smallestPrimeFactor = getSmallestPrimeFactors(X) divisors = [ getDivisors(x, smallestPrimeFactor) for x in a ] indices = [ [] for _ in xrange(X+1) ] for i, x in enumerate(a): indices[x].append(i) offsets = [None] * N numTotalDivisors = 0 for i in xrange(N): offsets[i] = numTotalDivisors numTotalDivisors += len(divisors[i]) nodes = [ Node(i) for i in xrange(N) for _ in xrange(len(divisors[i])) ] heads = [ None ] * (X+1) for x in xrange(X, 0, -1): for i in indices[x]: for j, d in enumerate(divisors[i]): heads[d] = insertToList(heads[d], nodes[offsets[i] + j]) curi = 0 ans = [ a[curi] ] for k in xrange(N-1): for j, d in enumerate(divisors[curi]): heads[d] = removeFromList(heads[d], nodes[offsets[curi] + j]) p = (X+1, X+1, -1) for j, d in enumerate(divisors[curi]): t = heads[d] if t: i = t.i p = min(p, (a[i] // d, a[i], i)) curi = p[2] ans.append(a[curi]) print " ".join(map(str, ans))