結果

問題 No.2025 Select $k$-th Submultiset
ユーザー lam6er
提出日時 2025-03-31 18:00:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,191 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 106,032 KB
最終ジャッジ日時 2025-03-31 18:01:21
合計ジャッジ時間 4,829 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

def comb(n, k):
    if n < k or k < 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_comb(s, m, c_list):
    total = 0
    n_subsets = 1 << m
    for mask in range(n_subsets):
        bits = bin(mask).count('1')
        sign = (-1) ** bits
        sum_S = 0
        for j in range(m):
            if mask & (1 << j):
                sum_S += c_list[j] + 1
        if sum_S > s:
            continue
        rem = s - sum_S
        curr_comb = comb(rem + m - 1, m - 1)
        total += sign * curr_comb
    return max(total, 0)

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    L = int(input[idx])
    idx += 1
    c = list(map(int, input[idx:idx+N]))
    idx += N
    Q = int(input[idx])
    idx += 1
    queries = []
    for _ in range(Q):
        queries.append(int(input[idx]))
        idx += 1
    
    total_comb = count_comb(L, N, c)
    
    for k in queries:
        if k > total_comb:
            print(-1)
            continue
        
        remaining_k = k
        sum_so_far = 0
        result = []
        for i in range(N):
            current_max = min(c[i], L - sum_so_far)
            found = False
            for a_i in range(current_max, -1, -1):
                s_remaining = (L - sum_so_far) - a_i
                if s_remaining < 0:
                    continue
                if i == N - 1:
                    ways = 1 if a_i == (L - sum_so_far) else 0
                else:
                    m = N - i - 1
                    c_remaining = c[i+1:]
                    ways = count_comb(s_remaining, m, c_remaining)
                if ways >= remaining_k:
                    result.append(a_i)
                    sum_so_far += a_i
                    found = True
                    break
                else:
                    remaining_k -= ways
            if not found:
                print(-1)
                break
        else:
            print(' '.join(map(str, result)))
    
if __name__ == "__main__":
    main()
0