結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N, L = int(input[idx]), int(input[idx+1])
    idx +=2
    c = list(map(int, input[idx:idx+N]))
    idx +=N
    Q = int(input[idx])
    idx +=1
    ks = []
    for _ in range(Q):
        ks.append(int(input[idx]))
        idx +=1
    
    def compute_total():
        m = N
        sum_c = sum(c)
        if sum_c < L:
            return 0
        res = 0
        for mask in range(0, 1 << m):
            bits = bin(mask).count('1')
            sum_S_plus1 = 0
            for i in range(m):
                if (mask >> i) & 1:
                    sum_S_plus1 += (c[i] +1)
            if sum_S_plus1 > L:
                continue
            s_prime = L - sum_S_plus1
            k_val = m-1
            if s_prime <0:
                continue
            # Compute C(s_prime + m-1, m-1)
            if s_prime + k_val < 0:
                comb =0
            else:
                n = s_prime + m -1
                k = k_val
                if k <0:
                    comb =0
                else:
                    if k ==0:
                        comb=1
                    elif k ==1:
                        comb =n
                    elif k ==2:
                        comb = n*(n-1)//2
                    elif k ==3:
                        comb = n*(n-1)*(n-2)//6
                    else:
                        comb =0  # for k>3, but m<=4
            res += (-1)**bits * comb
        return max(res,0)
    
    total = compute_total()
    
    if total ==0:
        for _ in range(Q):
            print(-1)
        return
    
    def compute_count(s, vars):
        m = len(vars)
        if m ==0:
            return 1 if s ==0 else 0
        res =0
        for mask in range(0, 1<<m):
            bits = bin(mask).count('1')
            sum_S_plus1 =0
            for i in range(m):
                if (mask >>i) &1:
                    sum_S_plus1 += (vars[i]+1)
            if sum_S_plus1 > s:
                continue
            s_prime = s - sum_S_plus1
            if s_prime <0:
                continue
            n = s_prime + m -1
            k_val = m-1
            if k_val >n:
                comb =0
            else:
                if k_val ==0:
                    comb=1
                elif k_val ==1:
                    comb =n
                elif k_val ==2:
                    comb =n*(n-1)//2
                elif k_val ==3:
                    comb =n*(n-1)*(n-2)//6
                else:
                    comb =0
            res += ((-1)**bits) * comb
        return max(res,0)
    
    for k in ks:
        if k > total:
            print(-1)
            continue
        current_k = k
        x = [0]*N
        remaining_L = L
        possible = True
        for i in range(N):
            ci = c[i]
            max_xi = min(ci, remaining_L)
            found = False
            for xi_candidate in range(max_xi, -1, -1):
                new_remaining = remaining_L - xi_candidate
                next_vars = c[i+1:]
                cnt = compute_count(new_remaining, next_vars)
                if cnt >= current_k:
                    x[i] = xi_candidate
                    remaining_L = new_remaining
                    found = True
                    break
                else:
                    current_k -= cnt
            if not found:
                possible = False
                break
        if not possible or remaining_L !=0:
            print(-1)
        else:
            print(' '.join(map(str, x)))
    
if __name__ == "__main__":
    main()
0