結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー tomerun
提出日時 2025-08-22 22:18:07
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 1,183 bytes
コンパイル時間 12,931 ms
コンパイル使用メモリ 311,420 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2025-08-22 22:19:00
合計ジャッジ時間 44,049 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

INF = 1 << 29
n, q = read_line.split.map(&.to_i)
s = read_line.chars.map(&.to_i)
pos = Array.new(10) { [] of Int32 }
n.times { |i| pos[s[i]] << i }
ds = [] of Tuple(Int32, Int32, Int32)
0.step(to: 999, by: 8) do |i|
  ds << {i % 10, i // 10 % 10, i // 100 % 10}
end
ds.select! { |v| !v.includes?(0) }
q.times do
  l, r = read_line.split.map { |v| v.to_i - 1 }
  ans = INF
  right = 10.times.map do |i|
    p = pos[i].bsearch_index { |v, _| v > r }
    if p
      p - 1
    else
      pos[i].size - 1
    end
  end.to_a
  ds.each do |d0, d1, d2|
    if right[d0] < 0 || pos[d0][right[d0]] < l
      next
    end
    i0 = pos[d0][right[d0]]
    right[d0] -= 1
    if right[d1] < 0 || pos[d1][right[d1]] < l
      right[d0] += 1
      next
    end
    i1 = pos[d1][right[d1]]
    right[d1] -= 1
    if right[d2] < 0 || pos[d2][right[d2]] < l
      right[d0] += 1
      right[d1] += 1
      next
    end
    i2 = pos[d2][right[d2]]
    c = r - i0
    i1 -= 1 if i1 > i0
    i2 -= 1 if i2 > i0
    c += (r - 1) - i1
    i2 -= 1 if i2 > i1
    c += (r - 2) - i2
    ans = {ans, c}.min
    # puts [d0, d1, d2, c]
    right[d0] += 1
    right[d1] += 1
  end
  puts ans == INF ? -1 : ans
end
0