結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2016-03-04 19:43:17 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 834 ms / 2,000 ms |
コード長 | 1,044 bytes |
コンパイル時間 | 527 ms |
コンパイル使用メモリ | 7,296 KB |
実行使用メモリ | 27,904 KB |
最終ジャッジ日時 | 2024-06-22 16:24:28 |
合計ジャッジ時間 | 12,639 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
Syntax OK
ソースコード
#配列aが昇順にソートされた状態を保ったまま要素nを入れる場合に、 #どの位置にインサートすればよいかを返す。 def insert_index(a, n) l = 0 r = a.length return 0 if r == 0 while l < r do m = (l + r) / 2 case n <=> a[m] when 1 then return m + 1 if r - l <= 1 l = m when 0 then return m + 1 when -1 then return m if r - l <= 1 r = m end end end gets a = gets.split.map(&:to_i) max_idxs = Hash.new{} #数が最後に現れるインデックスを格納する。 a.each.with_index do |n, idx| max_idxs[n] = idx end ans = [] open_nums = [] #今までに現れた数。要素は昇順にソートされている。出力に不要となった要素は削除される。 a.each.with_index do |n, idx| open_nums.insert(insert_index(open_nums, n), n) open_nums.pop while open_nums.size > 0 && idx > max_idxs[open_nums[-1]] #末尾の数がもう現れない数の場合、削除する。 ans << open_nums[-1] end puts ans.join(" ")