結果

問題 No.332 数列をプレゼントに
ユーザー lam6er
提出日時 2025-03-26 16:00:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,742 bytes
コンパイル時間 378 ms
コンパイル使用メモリ 82,680 KB
実行使用メモリ 85,292 KB
最終ジャッジ日時 2025-03-26 16:01:20
合計ジャッジ時間 4,363 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 1 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from itertools import combinations

    n, x = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    # Filter out elements greater than X and check for elements equal to X
    filtered = []
    for num in a:
        if num == x:
            # Directly output the result if found
            res = ['x'] * n
            for i in range(n):
                if a[i] == x:
                    res[i] = 'o'
                    print(''.join(res))
                    return
        if num <= x:
            filtered.append(num)
    
    # If no elements left after filtering
    if not filtered:
        print("No")
        return
    
    # Check if sum of filtered equals X
    total = sum(filtered)
    if total == x:
        res = []
        for num in a:
            if num > x:
                res.append('x')
            else:
                res.append('o')
        print(''.join(res))
        return
    if total < x:
        print("No")
        return
    
    # Now, check for subset sum
    len_filtered = len(filtered)
    indices = [i for i, num in enumerate(a) if num <= x]
    filtered_with_indices = [(num, idx) for num, idx in zip(filtered, indices)]
    
    # Function to generate all possible subset sums and their indices
    def generate_sums(arr):
        sums = {}
        n = len(arr)
        for i in range(1 << n):
            s = 0
            idxs = []
            for j in range(n):
                if (i >> j) & 1:
                    s += arr[j][0]
                    idxs.append(arr[j][1])
            if s not in sums:
                sums[s] = idxs
            # Prefer smaller subsets in case of multiple possibilities
            if len(idxs) < len(sums[s]):
                sums[s] = idxs
        return sums
    
    # Split into two halves
    half = len_filtered // 2
    first_half = filtered_with_indices[:half]
    second_half = filtered_with_indices[half:]
    
    sum1 = generate_sums(first_half)
    sum2 = generate_sums(second_half)
    
    found = False
    best = None
    for s1 in sum1:
        s2 = x - s1
        if s2 in sum2:
            # Combine the indices
            idxs = sum1[s1] + sum2[s2]
            if not best or len(idxs) < len(best):
                best = idxs
            found = True
    
    if found:
        res = ['x'] * n
        for idx in best:
            res[idx] = 'o'
        print(''.join(res))
        return
    
    # If len(filtered) > 40, then each element is small (product constraint)
    # But we have to handle it, but previous code already handles meet-in-middle for len <=40
    # So if we reach here, answer is No
    print("No")

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