結果

問題 No.14 最小公倍数ソート
ユーザー nsd_fbnsd_fb
提出日時 2015-02-20 09:18:46
言語 Python2
(2.7.18)
結果
AC  
実行時間 503 ms / 5,000 ms
コード長 1,030 bytes
コンパイル時間 138 ms
コンパイル使用メモリ 7,072 KB
実行使用メモリ 21,296 KB
最終ジャッジ日時 2024-06-23 21:22:22
合計ジャッジ時間 7,631 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 24 ms
8,960 KB
testcase_01 AC 28 ms
8,960 KB
testcase_02 AC 25 ms
8,960 KB
testcase_03 AC 64 ms
10,112 KB
testcase_04 AC 503 ms
21,296 KB
testcase_05 AC 263 ms
16,016 KB
testcase_06 AC 292 ms
16,544 KB
testcase_07 AC 351 ms
17,728 KB
testcase_08 AC 411 ms
19,052 KB
testcase_09 AC 473 ms
20,504 KB
testcase_10 AC 471 ms
20,380 KB
testcase_11 AC 484 ms
20,900 KB
testcase_12 AC 491 ms
20,908 KB
testcase_13 AC 490 ms
20,780 KB
testcase_14 AC 480 ms
20,776 KB
testcase_15 AC 494 ms
21,036 KB
testcase_16 AC 302 ms
16,408 KB
testcase_17 AC 248 ms
15,216 KB
testcase_18 AC 167 ms
13,312 KB
testcase_19 AC 392 ms
18,392 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import fractions
import heapq

def lcm(a, b):
    return a / fractions.gcd(a, b) * b

MAX_A = 10000

N = input()
A = map(int, raw_input().split())

divisor = [[] for _ in xrange(N)]
queue = [[] for _ in xrange(MAX_A + 1)]
used = [False] * N

for i, a in enumerate(A):
    j = 1
    
    while j * j <= a:
        if a % j == 0:
            divisor[i].append(j)
            heapq.heappush(queue[j], (a, i))
            
            if a / j != j:
                divisor[i].append(a / j)
                heapq.heappush(queue[a / j], (a, i))

        j += 1


ans = range(N)
for i in xrange(N - 1):
    index = ans[i]
    used[index] = True
    best = (float("inf"), -1, -1)

    for d in divisor[index]:
        que = queue[d]
        while que:
            tmp = que[0]
            if used[tmp[1]]:
                heapq.heappop(que)
                continue

            best = min(best, (lcm(A[index], tmp[0]),  tmp[0], tmp[1]))
            break

    ans[i + 1] = best[2]

print ' '.join(map(lambda index: str(A[index]), ans))
0