結果

問題 No.14 最小公倍数ソート
ユーザー nsd_fbnsd_fb
提出日時 2015-02-20 09:18:46
言語 Python2
(2.7.18)
結果
AC  
実行時間 466 ms / 5,000 ms
コード長 1,030 bytes
コンパイル時間 47 ms
コンパイル使用メモリ 6,668 KB
実行使用メモリ 20,620 KB
最終ジャッジ日時 2023-09-06 02:27:01
合計ジャッジ時間 7,313 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 23 ms
8,392 KB
testcase_01 AC 23 ms
8,256 KB
testcase_02 AC 23 ms
8,188 KB
testcase_03 AC 59 ms
9,464 KB
testcase_04 AC 466 ms
20,620 KB
testcase_05 AC 247 ms
15,268 KB
testcase_06 AC 276 ms
16,004 KB
testcase_07 AC 321 ms
17,152 KB
testcase_08 AC 375 ms
18,552 KB
testcase_09 AC 444 ms
19,744 KB
testcase_10 AC 432 ms
19,892 KB
testcase_11 AC 445 ms
20,452 KB
testcase_12 AC 451 ms
20,232 KB
testcase_13 AC 451 ms
20,312 KB
testcase_14 AC 453 ms
20,088 KB
testcase_15 AC 457 ms
20,288 KB
testcase_16 AC 276 ms
15,728 KB
testcase_17 AC 227 ms
14,672 KB
testcase_18 AC 155 ms
12,556 KB
testcase_19 AC 358 ms
18,044 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