更新日時で差をつけろ

差をつけられそう

JOI 難易度5: JOI国のお散歩事情

こうじゃね?って5分ぐらいで浮かんで、2時間ぐらいかけて実装したけどWA。うっ、こころがくるしい
解説見たら方向性間違ってました…見てもよくわからなさすぎて面白くないので今日の2問実装したらABC埋めに戻りたい〜〜〜〜

6/20(追記)

解説を見て書き直してみました。すっきり。 だがWAです。多分"ここ"と"そこ"を改善すれば通るはず…飯食って風呂入ってからやり直したけど通りませんでした。 流石に諦めて別の問題に映るべきなのかなと…

# 解説を見た
n, t, q = gets.split.map(&:to_i)
a = [] # go east -> 1, west -> -1
n.times do |i|
  l = gets.split.map(&:to_i)
  # [ 座標Ai, 東向きを正として1/-1, Xiに含まれるか, (時間が無限にあった場合)どこで止まるか ]
  a << [l[0],  1, false, nil] if l[1] == 1
  a << [l[0], -1, false, nil] if l[1] == 2
end

q.times do
  x = gets.to_i - 1
  a[x][2] = true
end

latest_east = []
a.each_with_index do |c, i|
  if c[1] == 1
    latest_east << i
  else
    next if latest_east.empty?
    # p [latest_east, a[latest_east.last]]
    if a[latest_east.last][3]
      c[3] = a[latest_east.last][3]
    else
      middle = (c[0] + a[latest_east.last][0]) / 2
      latest_east.each { |b| a[b][3] = middle }
      c[3] = a[latest_east.last][3]
      latest_east = [latest_east.last]
    end
  end
end
# p a

a.each_with_index do |c, i|
  c[0] += c[1] * t
  c[0] = [c[0], c[3] || -99999999999999].max if c[1] == -1
  c[0] = [c[0], c[3] || 99999999999999].min if c[1] == 1
end

# p t, a

a.reverse.each_cons(2) do |c, d|
  d[0] = [c[0], d[0]].min
end

a.each do |c|
  puts c[0] if c[2]
end

6/19

いかにもバグがでそうなコードですね。明日実装しよ…(明日やろうはバカやろうですが、勉強をするので)

n, t, q = gets.split.map(&:to_i)
a = [] # go east -> 1, west -> -1
n.times do |i|
  l = gets.split.map(&:to_i)
  a << [l[0],  1, false, true, i] if l[1] == 1 # [ 座標Ai, 東向きを正として1/-1, Xiに含まれるか, まだ動くか(立ち話してないか), i ]
  a << [l[0], -1, false, true, i] if l[1] == 2
end
q.times do
  x = gets.to_i - 1
  a[x][2] = true
end

pos = []
(t/2).times do |ti|
  cur = 0
  new_a = []
  while cur < a.size
    c = a[cur]
    unless c[3]
      new_a << c
      cur += 1
      next
    end

    if !new_a.empty? && new_a[-1][0] == c[0] + 2 * c[1]
      new_a[-1][3] = false
    elsif !new_a.empty? && new_a[-1][0] > c[0] + 2 * c[1]
      new_a[-1][0] = new_a[-1][0] - new_a[-1][1]
      new_a[-1][3] = false
    elsif !new_a.empty? && new_a[-1][0] > c[0]
      new_a[-1][0] = c[0]
      new_a[-1][3] = false
    else
      new_a << [c[0] + 2 * c[1], c[1], c[2], c[3], c[4]]
    end
    if c[2]
      new_a[-1][2] = true
      pos[c[4]] = new_a[-1][0]
    end
    cur += 1
  end
  a = new_a
end

if t % 2 == 1
  cur = 0
  new_a = []
  while cur < a.size
    c = a[cur]
    unless c[3]
      cur += 1
      next
    end
    if !new_a.empty? && new_a[-1][0] == c[0] + c[1]
      new_a[-1][3] = false
    else
      new_a << [c[0] + c[1], c[1], c[2], c[3], c[4]]
    end
    if c[2]
      new_a[-1][2] = true
      pos[c[4]] = new_a[-1][0]
    end
    cur += 1
  end
  a = new_a
end

a.each do |c|
  if c[2]
    pos[c[4]] = c[0]
  end
end

pos.each_with_index do |v, i|
  puts [v, pos[i+1] || 999999999999].min if v
end