結果

問題 No.332 数列をプレゼントに
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:55:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,837 bytes
コンパイル時間 743 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 81,536 KB
最終ジャッジ日時 2025-05-14 12:56:39
合計ジャッジ時間 11,688 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    X = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N

    sum_total = sum(A)
    if sum_total < X:
        print("No")
        return

    B = []
    for a in A:
        if a <= X:
            B.append(a)
    sum_B = sum(B)
    if sum_B < X:
        print("No")
        return

    ones_indices = []
    non_ones = []
    for i, a in enumerate(A):
        if a <= X:
            if a == 1:
                ones_indices.append(i)
            else:
                non_ones.append((a, i))

    count_ones = len(ones_indices)
    sum_non_ones = sum(a for a, i in non_ones)
    lower_T = max(0, X - count_ones)
    upper_T = min(sum_non_ones, X)

    for T in range(lower_T, upper_T + 1):
        required_ones = X - T
        if required_ones < 0 or required_ones > count_ones:
            continue

        if not non_ones:
            if T == 0 and required_ones <= count_ones:
                res = ['x'] * N
                for i in range(required_ones):
                    res[ones_indices[i]] = 'o'
                print(''.join(res))
                return
            else:
                continue

        m = len(non_ones)
        first_half = non_ones[:m//2]
        second_half = non_ones[m//2:]

        sum_to_mask1 = {}
        for mask in range(0, 1 << len(first_half)):
            s = 0
            for i in range(len(first_half)):
                if mask & (1 << i):
                    s += first_half[i][0]
            if s not in sum_to_mask1:
                sum_to_mask1[s] = mask

        sum_to_mask2 = {}
        for mask in range(0, 1 << len(second_half)):
            s = 0
            for i in range(len(second_half)):
                if mask & (1 << i):
                    s += second_half[i][0]
            if s not in sum_to_mask2:
                sum_to_mask2[s] = mask

        found = False
        for s1 in sum_to_mask1:
            s2 = T - s1
            if s2 in sum_to_mask2:
                mask1 = sum_to_mask1[s1]
                mask2 = sum_to_mask2[s2]
                indices = []
                for i in range(len(first_half)):
                    if mask1 & (1 << i):
                        indices.append(first_half[i][1])
                for i in range(len(second_half)):
                    if mask2 & (1 << i):
                        indices.append(second_half[i][1])
                res = ['x'] * N
                for idx in indices:
                    res[idx] = 'o'
                for i in range(required_ones):
                    if i < len(ones_indices):
                        res[ones_indices[i]] = 'o'
                print(''.join(res))
                return

    print("No")

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