結果

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

ソースコード

diff # 

import sys

def combination(n, k):
    if n < 0:
        return 0
    if k == 0:
        return 1
    if k == 1:
        return n
    if k == 2:
        return n * (n - 1) // 2
    if k == 3:
        return n * (n - 1) * (n - 2) // 6
    return 0

def count_tuples(c, r):
    n = len(c)
    if n == 0:
        return 1 if r == 0 else 0
    total = 0
    for mask in range(1 << n):
        bits = bin(mask).count('1')
        s = 0
        for j in range(n):
            if (mask >> j) & 1:
                s += (c[j] + 1)
        if s > r:
            continue
        comb = combination(r - s + (n - 1), n - 1)
        term = (-1) ** bits * comb
        total += term
    return total

def main():
    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]))
    ptr += Q

    for k in queries:
        total = count_tuples(c, L)
        if total < k:
            print(-1)
            continue
        a = [0] * (N + 1)
        remaining = L
        for i in range(1, N + 1):
            current_c = c[i - 1]
            max_a = min(current_c, remaining)
            for a_candidate in range(max_a, -1, -1):
                new_remaining = remaining - a_candidate
                if i == N:
                    if new_remaining == 0:
                        cnt = 1
                    else:
                        cnt = 0
                else:
                    cnt = count_tuples(c[i:], new_remaining)
                if cnt >= k:
                    a[i] = a_candidate
                    remaining = new_remaining
                    break
                else:
                    k -= cnt
            else:
                a[i] = 0
        print(' '.join(map(str, a[1:N+1])))

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