結果

問題 No.1730 GCD on Blackboard in yukicoder
ユーザー lam6er
提出日時 2025-03-31 17:42:55
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,393 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 670,404 KB
最終ジャッジ日時 2025-03-31 17:44:22
合計ジャッジ時間 11,893 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    if N == 0:
        return
    
    max_A = max(A) if A else 0

    # Frequency array
    freq = [0] * (max_A + 2)
    for a in A:
        freq[a] += 1
    
    # Calculate cnt array
    cnt = [0] * (max_A + 2)
    for d in range(1, max_A + 1):
        multiple = d
        while multiple <= max_A:
            cnt[d] += freq[multiple]
            multiple += d
    
    # Collect d candidates in descending order
    d_candidates = []
    for d in range(max_A, 0, -1):
        if cnt[d] > 0:
            d_candidates.append(d)
    
    # Initialize answer array and Union-Find structure
    ans = [0] * N
    uf_parent = list(range(N + 2))  # 0..N inclusive

    def find(x):
        if uf_parent[x] != x:
            uf_parent[x] = find(uf_parent[x])
        return uf_parent[x]
    
    # Process each d in descending order
    for d in d_candidates:
        required = N - cnt[d]
        k_min = max(0, required)
        if k_min >= N:
            continue
        current = find(k_min)
        while current < N:
            ans[current] = d
            uf_parent[current] = current + 1
            current = find(current)
    
    # Print the results
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()
0