結果

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

ソースコード

diff # 

import sys

def compute_count(m, L_prime, c_list):
    if m == 0:
        return 1 if L_prime == 0 else 0
    total = 0
    for mask in range(0, 1 << m):
        bits = bin(mask).count('1')
        sum_c = 0
        for i in range(m):
            if (mask >> i) & 1:
                sum_c += c_list[i] + 1
        t = L_prime - sum_c + (m - 1)
        if t < 0:
            continue
        if m - 1 == 0:
            comb = 1
        elif m - 1 == 1:
            comb = t if t >= 0 else 0
        elif m - 1 == 2:
            if t < 2:
                comb = 0
            else:
                comb = t * (t - 1) // 2
        elif m - 1 == 3:
            if t < 3:
                comb = 0
            else:
                comb = t * (t - 1) * (t - 2) // 6
        else:
            comb = 0
        if bits % 2 == 0:
            total += comb
        else:
            total -= comb
    return max(total, 0)

def solve():
    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
    k_list = list(map(int, input[idx:idx+Q]))
    idx +=Q
    
    for k in k_list:
        m_total = compute_count(N, L, c)
        if m_total < k or m_total ==0:
            print(-1)
            continue
        x = [0]*N
        remaining = L
        possible = True
        for v in range(N):
            max_x_v = min(c[v], remaining)
            found = False
            for x_v in range(max_x_v, -1, -1):
                rem = remaining - x_v
                m = N - v -1
                if m ==0:
                    cnt = 1 if rem ==0 else 0
                else:
                    cnt = compute_count(m, rem, c[v+1:])
                if cnt < k:
                    k -= cnt
                else:
                    x[v] = x_v
                    remaining = rem
                    found = True
                    break
            if not found:
                possible = False
                break
        if possible:
            print(' '.join(map(str, x)))
        else:
            print(-1)

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