結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー fungsi
提出日時 2025-09-08 22:20:29
言語 Crystal
(1.14.0)
結果
RE  
実行時間 -
コード長 1,543 bytes
コンパイル時間 10,719 ms
コンパイル使用メモリ 312,364 KB
実行使用メモリ 205,720 KB
最終ジャッジ日時 2025-09-08 22:20:57
合計ジャッジ時間 24,001 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, q = gets.not_nil!.split.map(&.to_i)
s = gets.not_nil!.chomp

# Initialize x with 3D array
x = Array(Array(Array(Int32))).new(1) do
  Array.new(10) { [-1] * 3 }
end

# Build the x array
s.chars.each_with_index do |char, idx|
  now = x.last.map(&.dup)
  digit = char.to_i
  now[digit] = now[digit][1..] + [idx]
  x << now
end

# Generate q array
q_list = [] of Array(Int32)
(0...1000).each do |i|
  next if i % 8 != 0
  q_list << [i // 100, (i % 100) // 10, i % 10]
end

inf = 10**18

def calc(a, b, c, r)
  ans = 0
  ans += r - c
  if b > c
    b -= 1
  end
  if a > c
    a -= 1
  end
  ans += r - b - 1
  if a > b
    a -= 1
  end
  ans += r - a - 2
  ans
end

q.times do
  l, r = gets.not_nil!.split.map(&.to_i)
  ans = inf
  
  if l == r
    if s[r - 1] == '8'
      puts 0
    else
      puts -1
    end
    next
  end
  
  if l + 1 == r
    num1 = (s[l - 1].to_i * 10 + s[r - 1].to_i) % 8
    num2 = (s[r - 1].to_i * 10 + s[l - 1].to_i) % 8
    if num1 == 0
      puts 0
    elsif num2 == 0
      puts 1
    else
      puts -1
    end
    next
  end
  
  p = x[r]
  q_list.each do |triplet|
    a, b, c = triplet
    cnt = [0] * 10
    
    # Get positions from the precomputed array
    c_pos = p[c][-cnt[c] - 1]
    cnt[c] += 1
    b_pos = p[b][-cnt[b] - 1]
    cnt[b] += 1
    a_pos = p[a][-cnt[a] - 1]
    cnt[a] += 1
    
    if [a_pos, b_pos, c_pos].min >= l - 1
      current_ans = calc(a_pos, b_pos, c_pos, r - 1)
      ans = Math.min(ans, current_ans)
    end
  end
  
  if ans == inf
    puts -1
  else
    puts ans
  end
end
0