結果

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

ソースコード

diff # 

import sys
import math
from math import comb

def compute_total(c, L, N):
    m = N
    total = 0
    for mask in range(0, 1 << m):
        bits = bin(mask).count('1')
        sum_mask = 0
        for j in range(m):
            if mask & (1 << j):
                sum_mask += (c[j] + 1)
        if L - sum_mask < 0:
            continue
        ways = comb(L - sum_mask + m - 1, m - 1)
        if bits % 2 == 0:
            total += ways
        else:
            total -= ways
    return total if total > 0 else 0

def solve():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    L = int(input[ptr+1])
    ptr += 2
    c = list(map(int, input[ptr:ptr+N]))
    ptr += N
    Q = int(input[ptr])
    ptr += 1
    queries = list(map(int, input[ptr:ptr+Q]))
    
    total = compute_total(c, L, N)
    
    for k in queries:
        if k > total:
            print(-1)
            continue
        
        a = [0] * N
        remaining = L
        possible = True
        
        for v in range(N):
            if remaining == 0:
                break
            if v == N-1:
                if c[v] >= remaining:
                    a[v] = remaining
                    remaining = 0
                else:
                    possible = False
                    break
                continue
            
            m = N - v - 1
            current_c = c[v]
            a_max = min(current_c, remaining)
            s = remaining
            
            f = [0] * (s + 1)
            for t in range(s + 1):
                total_ways = 0
                for mask in range(0, 1 << m):
                    bits = bin(mask).count('1')
                    sum_mask = 0
                    for j in range(m):
                        if mask & (1 << j):
                            sum_mask += (c[v+1 + j] + 1)
                    if t - sum_mask < 0:
                        continue
                    n = t - sum_mask
                    k_comb = comb(n + m - 1, m - 1) if n + m - 1 >= m -1 else 0
                    if bits % 2 == 0:
                        total_ways += k_comb
                    else:
                        total_ways -= k_comb
                f[t] = total_ways
            
            pre = [0] * (s + 2)
            for t in range(s + 1):
                pre[t+1] = pre[t] + f[t]
            
            low = 0
            high = a_max
            best_a = -1
            while low <= high:
                mid = (low + high) // 2
                t = s - mid
                if t < 0:
                    current = 0
                else:
                    t1 = s - a_max
                    t2 = s - mid
                    if t1 > t2:
                        current = 0
                    else:
                        if t1 < 0:
                            t1 = 0
                        if t2 > s:
                            t2 = s
                        current = pre[t2 + 1] - pre[t1]
                if current >= k:
                    best_a = mid
                    low = mid + 1
                else:
                    high = mid - 1
            
            if best_a == -1:
                possible = False
                break
            
            t1 = s - a_max
            t2 = s - (best_a + 1)
            if t1 > t2:
                subtract = 0
            else:
                if t1 < 0:
                    t1 = 0
                if t2 > s:
                    t2 = s
                subtract = pre[t2 + 1] - pre[t1]
            k -= subtract
            a[v] = best_a
            remaining = s - best_a
        
        if possible and remaining == 0:
            print(' '.join(map(str, a)))
        else:
            print(-1)

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