結果
| 問題 | No.1730 GCD on Blackboard in yukicoder |
| コンテスト | |
| ユーザー |
tamato
|
| 提出日時 | 2021-11-05 22:21:42 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
TLE
不安定
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 780 bytes |
| 記録 | |
| コンパイル時間 | 568 ms |
| コンパイル使用メモリ | 64,512 KB |
| 実行使用メモリ | 211,776 KB |
| 最終ジャッジ日時 | 2026-11-04 22:15:08 |
| 合計ジャッジ時間 | 23,472 ms |
|
ジャッジサーバーID (参考情報) |
judge7_0 / judge4_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 TLE * 1 |
ソースコード
mod = 1000000007
eps = 10**-9
NN = 10 ** 6
def main():
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
div = [[] for _ in range(NN + 1)]
for i in range(1, NN+1):
for x in range(1, NN+1):
if i * x > NN:
break
if i * x in C:
div[i*x].append(i)
cnt = [N] * (NN+1)
for a in C:
k = C[a]
for d in div[a]:
cnt[d] -= k
ans = [1] * (N+1)
for x in range(1, NN+1):
k = cnt[x]
ans[k] = x
for i in range(1, N+1):
ans[i] = max(ans[i], ans[i-1])
for i in range(N):
print(ans[i])
if __name__ == '__main__':
main()
tamato