結果

問題 No.332 数列をプレゼントに
コンテスト
ユーザー code-devo
提出日時 2016-01-19 10:07:12
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 901 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 103 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 130,944 KB
最終ジャッジ日時 2024-09-21 07:59:47
合計ジャッジ時間 10,722 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 39 WA * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

N, X = gets.split.map(&:to_i)
NS = gets.split.map(&:to_i)

def print_ans(idxs)
  puts (0...N).map{|i| idxs.include?(i) ? "o" : "x"}.join
  exit #こんなところでexitは使いたくないが・・・
end

nis = NS.map.with_index{|n,idx| [n,idx]}.select{|a| a[0] <= X}.sort

hash1 = Hash.new
hash1[0] = []
while ni = nis.shift do
  num, idx = ni
  add = {}
  hash1.each do |sum, idxs|
    new_sum = sum + num
    print_ans(idxs.dup << idx) if new_sum == X
    add[new_sum] = idxs.dup << idx if new_sum < X && !hash1[new_sum]
  end  
  hash1.update(add)
  break if hash1.size >= 100_000
end

hash2 = Hash.new
hash2[0] = []
while ni = nis.shift do
  num, idx = ni
  add = {}
  hash2.each do |sum, idxs|
    new_sum = sum + num
    print_ans(hash1[X - new_sum] + idxs) if hash1[X - new_sum]
    add[new_sum] = idxs.dup << idx if new_sum < X && !hash2[new_sum]
  end
  hash2.update(add)
end

puts "No"
0