結果

問題 No.3269 Leq-K Partition
ユーザー とりゐ
提出日時 2025-09-12 23:41:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,758 ms / 6,000 ms
コード長 741 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,852 KB
実行使用メモリ 259,416 KB
最終ジャッジ日時 2025-09-12 23:46:55
合計ジャッジ時間 24,724 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge10
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://codeforces.com/blog/entry/134445

n = int(input())
C = list(map(lambda x: int(x) - 1, input().split()))

A = [0] * (n + 2)
A[0] = n + 1
A[n + 1] = 0


def f(k):
    # find a_k
    memo = [-1] * n
    tmp = 0
    cnt = 0
    res = 0
    for i in C:
        if memo[i] != tmp:
            if cnt == k:
                res += 1
                cnt = 0
                tmp += 1
            cnt += 1
            memo[i] = tmp
    return res


def search(l, r):
    if l > r:
        return
    if A[l - 1] == A[r + 1]:
        for x in range(l, r + 1):
            A[x] = A[l - 1]
        return
    m = (l + r) // 2
    A[m] = f(m)
    search(l, m - 1)
    search(m + 1, r)


search(1, n)
for i in range(1, n + 1):
    print(A[i] + 1)
0