N, X = gets.split.map(&:to_i) NS = gets.split.map(&:to_i) nis = NS.map.with_index{|n,idx| [n,idx]}.select{|ni| ni[0] <= X}.sort ans = catch(:ok) do #DPを使用し、作成できる和を求める。 #ただし、要素が10000以上になったところで計算をやめる。 #(全ての要素に対して行うと、計算が終わらないため) dp1 = {} dp1[0] = [] while ni = nis.shift do num, idx = ni add = {} dp1.each do |sum, idxs1| new_sum = sum + num throw :ok, idxs1.dup << idx if new_sum == X add[new_sum] = idxs1.dup << idx if new_sum < X && !dp1[new_sum] end dp1.update(add) break if dp1.size >= 10_000 end #上記で使用しなかった要素について、再度DPで作成できる和を求める。 #上記で求めた和のいずれかと合わせてXとなれば、解の発見となる。 dp2 = {} dp2[0] = [] while ni = nis.shift do num, idx = ni add = {} dp2.each do |sum, idxs2| new_sum = sum + num throw :ok, (dp1[X - new_sum] + idxs2) << idx if dp1[X - new_sum] add[new_sum] = idxs2.dup << idx if new_sum < X && !dp2[new_sum] end dp2.update(add) end nil end puts ans ? (0...N).map{|i| ans.include?(i) ? "o" : "x"}.join : "No"