結果

問題 No.332 数列をプレゼントに
ユーザー gew1fw
提出日時 2025-06-12 14:17:30
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,734 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 424,936 KB
最終ジャッジ日時 2025-06-12 14:17:42
合計ジャッジ時間 5,538 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 MLE * 1
other AC * 18 MLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd

n, x = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

remaining_indices = []
remaining_elements = []
for i in range(n):
    if a[i] <= x:
        remaining_indices.append(i)
        remaining_elements.append(a[i])

m = len(remaining_elements)
sum_remaining = sum(remaining_elements)

if sum_remaining < x:
    print("No")
    sys.exit()

# Check if any element equals x
for i in range(m):
    if remaining_elements[i] == x:
        res = ['x'] * n
        res[remaining_indices[i]] = 'o'
        print(''.join(res))
        sys.exit()

if sum_remaining == x:
    res = ['x'] * n
    for idx in remaining_indices:
        res[idx] = 'o'
    print(''.join(res))
    sys.exit()

D = sum_remaining - x

# Calculate GCD of remaining elements
current_gcd = 0
for num in remaining_elements:
    current_gcd = gcd(current_gcd, num)
if D % current_gcd != 0:
    print("No")
    sys.exit()

# Dynamic programming to find subset sum D
prev = {0: None}
for i in range(m):
    ai = remaining_elements[i]
    current_sums = list(prev.keys())
    for s in current_sums:
        new_s = s + ai
        if new_s > D:
            continue
        if new_s not in prev:
            prev[new_s] = i

if D not in prev:
    print("No")
    sys.exit()

# Backtrack to find used elements
current_sum = D
used = set()
while current_sum > 0:
    i = prev[current_sum]
    used.add(i)
    current_sum -= remaining_elements[i]

# Construct the result
res = ['x'] * n
for idx_in_remaining in range(m):
    original_idx = remaining_indices[idx_in_remaining]
    if idx_in_remaining not in used:
        res[original_idx] = 'o'
    else:
        res[original_idx] = 'x'

print(''.join(res))
0