結果

問題 No.2025 Select $k$-th Submultiset
ユーザー gew1fw
提出日時 2025-06-12 15:27:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,135 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 78,800 KB
最終ジャッジ日時 2025-06-12 15:27:26
合計ジャッジ時間 5,091 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import comb as math_comb

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    L = int(input[ptr]); ptr +=1
    c = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    Q = int(input[ptr]); ptr +=1
    queries = list(map(int, input[ptr:ptr+Q]))
    
    # Precompute factorials and inverse factorials if needed
    # But for small k, we can compute comb directly
    
    memo = {}
    
    def compute_f(j, rem):
        if j > N:
            return 1 if rem == 0 else 0
        key = (j, rem)
        if key in memo:
            return memo[key]
        c_list = c[j-1:N]
        m = len(c_list)
        total = 0
        for mask in range(0, 1 << m):
            bits = bin(mask).count('1')
            s = 0
            for i in range(m):
                if mask & (1 << i):
                    s += c_list[i] + 1
            if rem < s:
                continue
            sign = (-1) ** bits
            n = rem - s + (m - 1)
            k = m - 1
            if n < 0 or k < 0 or k > n:
                term = 0
            else:
                term = math_comb(n, k)
            total += sign * term
        memo[key] = total
        return total
    
    for k_val in queries:
        total = compute_f(1, L)
        if total < k_val:
            print(-1)
            continue
        counts = [0] * N
        rem = L
        for i in range(1, N + 1):
            max_a = min(c[i-1], rem)
            found = False
            for a in range(max_a, -1, -1):
                new_rem = rem - a
                ways = compute_f(i + 1, new_rem)
                if ways >= k_val:
                    counts[i - 1] = a
                    rem = new_rem
                    found = True
                    break
                else:
                    k_val -= ways
            if not found:
                print(-1)
                break
        else:
            if sum(counts) != L:
                print(-1)
            else:
                print(' '.join(map(str, counts)))
    return

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