結果

問題 No.3269 Leq-K Partition
コンテスト
ユーザー 遭難者
提出日時 2025-07-28 13:58:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,159 bytes
コンパイル時間 672 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 266,992 KB
最終ジャッジ日時 2025-08-11 21:34:33
合計ジャッジ時間 7,992 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math


def solve():
    """
    Solves the problem by translating the C++ logic directly to Python.
    Note: The AtCoder library, custom operators, and helper templates from the C++
    code were not used in the core `solve` logic and are thus not included here.
    """
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return
        n = int(n_str)
        if n > 0:
            a = list(map(int, sys.stdin.readline().split()))
        else:
            a = []
    except (IOError, ValueError):
        return

    # In C++, `a--` decrements each element for 0-based indexing.
    a = [x - 1 for x in a]

    # `vec<int> ans(n + 1, 1);`
    ans = [1] * (n + 1)

    # The lambda `f` in C++ is defined as a nested function `f_calc`.
    # It captures `n` and `a` from the outer scope.
    def f_calc(k):
        # Handle k=0 case, which is not expected by problem constraints (k>=1)
        # but can be called by the binary search. With k=0 allowed distinct
        # elements, every element requires a new group.
        if k == 0:
            return n if n > 0 else 0

        count = 1
        seen = [False] * n
        current_set = []
        for val in a:
            if seen[val]:
                continue
            seen[val] = True
            current_set.append(val)
            if len(current_set) == k + 1:
                for v_reset in current_set:
                    seen[v_reset] = False
                current_set.clear()
                count += 1
                seen[val] = True
                current_set.append(val)
        return count

    # Handle n=0 case to prevent math domain errors.
    if n == 0:
        return

    # `int b = min(n, (int)sqrt(n * log2(n)));`
    # The threshold `b` is calculated for the algorithm optimization.
    if n > 1:
        b = min(n, int((n * math.log2(n)) ** 0.5))
    else:  # Handles n=1
        b = 0

    # Brute-force calculation for small k
    for k in range(1, b + 1):
        ans[k] = f_calc(k)

    # Optimized calculation for large k using binary search
    le0 = b
    # `ans[b]` is the starting point for the number of groups (ss).
    # If b=0, C++ `ans[0]` is 1. Python `ans[0]` is also 1.
    start_ss = ans[b]

    for ss_val in range(start_ss, 0, -1):
        # Binary search to find the largest k that results in `ss_val` groups.
        # `f_calc` is non-increasing, so this works.
        ok = le0 - 1
        ng = n
        while ng - ok > 1:
            vs = (ok + ng) // 2
            # vs can become 0 if le0=1. f_calc handles this.
            if f_calc(vs) == ss_val:
                ok = vs
            else:  # f_calc(vs) < ss_val
                ng = vs

        # Fill the answer for the range of k found.
        # `ng` becomes the new lower bound for the next iteration's search.
        for k in range(le0, ng):
            ans[k] = ss_val
        le0 = ng

    # Print results
    for k in range(1, n + 1):
        print(ans[k])


def main():
    # Fast I/O
    sys.stdin = open(0)

    # The C++ code is set up for multiple test cases but runs only one.
    solve()


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