結果

問題 No.1730 GCD on Blackboard in yukicoder
ユーザー dn6049949dn6049949
提出日時 2021-11-05 22:08:30
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 264 ms / 2,000 ms
コード長 954 bytes
コンパイル時間 827 ms
コンパイル使用メモリ 86,592 KB
実行使用メモリ 110,284 KB
最終ジャッジ日時 2023-08-07 23:10:15
合計ジャッジ時間 8,065 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 257 ms
110,156 KB
testcase_01 AC 94 ms
71,388 KB
testcase_02 AC 197 ms
92,540 KB
testcase_03 AC 198 ms
92,604 KB
testcase_04 AC 201 ms
92,660 KB
testcase_05 AC 196 ms
92,784 KB
testcase_06 AC 196 ms
92,648 KB
testcase_07 AC 199 ms
92,812 KB
testcase_08 AC 96 ms
71,540 KB
testcase_09 AC 164 ms
88,512 KB
testcase_10 AC 165 ms
88,476 KB
testcase_11 AC 94 ms
71,396 KB
testcase_12 AC 94 ms
71,392 KB
testcase_13 AC 264 ms
110,072 KB
testcase_14 AC 260 ms
110,188 KB
testcase_15 AC 260 ms
109,800 KB
testcase_16 AC 258 ms
110,284 KB
testcase_17 AC 260 ms
110,172 KB
testcase_18 AC 172 ms
97,248 KB
testcase_19 AC 255 ms
109,980 KB
testcase_20 AC 221 ms
104,316 KB
testcase_21 AC 225 ms
104,352 KB
testcase_22 AC 221 ms
105,612 KB
testcase_23 AC 149 ms
96,752 KB
testcase_24 AC 245 ms
107,912 KB
testcase_25 AC 256 ms
109,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    m = max(a)+1
    f = [0]*m
    for i in a:
        f[i] += 1
    cnt = [0]*m
    for i in range(1,m):
        s = 0
        for j in range(i,m,i):
            s += f[j]
        cnt[i] = s
    ans = [0]*n
    for i in range(m)[::-1]:
        ci = cnt[i]-1
        if ci >= 0 and not ans[ci]:
            ans[ci] = i
    for i in range(n-1)[::-1]:
        ans[i] = max(ans[i],ans[i+1])
    for i in ans[::-1]:
        print(i)
    return


if __name__ == "__main__":
    solve()
0