Problem p03498 (python)

Fixed submission:
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# 最も絶対値の大きい数を、それが正の数なら右から、負の数なら左から、
# 昇順になっていない場所に足していく

# print(A)

ans = []
plusmax = 0
minusmax = 0
plusmax_i = -1
minusmax_i = -1
  
target = -1
maxdiff = 0
for i in range(len(A)):
  if A[i] < minusmax:
    minusmax = A[i]
    minusmax_i = i
  if A[i] > plusmax:
    plusmax = A[i]
    plusmax_i = i
# 最も絶対値が大きいものが正であれば、左から順に足していく
# 負であれば右から
# この方針は途中で変えない。正なら最後まで正。
# 2要素の差の最大値は、絶対値の最大がたとえば1000のときに1000～-1000の差なので、
# 2回足せば必ず差が埋まる
  
if abs(plusmax) > abs(minusmax):
  # 正でいく場合
  maxval = plusmax
  max_i = plusmax_i
  for i in range(1,len(A)):
    if A[i - 1] > A[i]:
      ans.append((max_i + 1,i + 1))
      ans.append((max_i + 1,i + 1))
      A[i] += 2 * maxval
      max_i = i
      maxval = A[i]
else:
  # 負でいく場合
  minval = minusmax
  min_i = minusmax_i
  for i in range(len(A) - 1, 0,-1):
    if A[i - 1] > A[i]:
      ans.append((min_i + 1, i))
      ans.append((min_i + 1, i))
      A[i - 1] += 2 * minval
      min_i = i - 1
      minval = A[i - 1]
        
print(len(ans))
for a in ans:
  print(*a)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# 最も絶対値の大きい数を、それが正の数なら右から、負の数なら左から、
# 昇順になっていない場所に足していく

# print(A)

ans = []
while True:
  plusmax = 0
  minusmax = 0
  plusmax_i = -1
  minusmax_i = -1
  
  target = -1
  maxdiff = 0
  for i in range(len(A)):
    if A[i] < minusmax:
      minusmax = A[i]
      minusmax_i = i
    if A[i] > plusmax:
      plusmax = A[i]
      plusmax_i = i
    # 正/負の方向に最も大きい数とそのインデックスを求めた
    if i != 0:
      if A[i - 1] > A[i]:
        diff = A[i - 1] - A[i]
        if diff <= maxdiff:
          continue
        maxdiff = diff
        target = i
  if target == -1:
    # 一度の逆転が起きていなければ終了
    break
  if abs(plusmax) > abs(minusmax):
    # 正の数の最大値のほうが大きい場合は右端に足す
    ans += [(plusmax_i + 1, target + 1)]
    # print(ans[-1])
    A[target] += plusmax
  else:
    # 負の数の最大値のほうが大きい場合は左端に足す
    ans += [(minusmax_i + 1, target)]
    # print(ans[-1])
    A[target - 1] += minusmax
  # print(A)
    
if len(ans) > 2 * N:
  p = 1 / 0
print(len(ans))
for a in ans:
  print(*a)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# 最も絶対値の大きい数を、それが正の数なら右から、負の数なら左から、
# 昇順になっていない場所に足していく

ans = []
while True:
  plusmax = 0
  minusmax = 0
  plusmax_i = -1
  minusmax_i = -1
  left_target = -1
  right_target = -1
  targetdiff = 0
  for i in range(len(A)):
    if A[i] < minusmax:
      minusmax = A[i]
      minusmax_i = i
    if A[i] > plusmax:
      plusmax = A[i]
      plusmax_i = i
    # 正/負の方向に最も大きい数とそのインデックスを求めた
    if i != 0:
      if A[i - 1] > A[i]:
        if left_target == -1: # 左端は一度しか更新しない
          left_target = i
        right_target = i # 右端は常に更新
  if left_target == -1:
    # 一度の逆転が起きていなければ終了
    break
  if abs(plusmax) > abs(minusmax):
    # 正の数の最大値のほうが大きい場合は右端に足す
    ans += [(plusmax_i + 1, right_target + 1)]
    A[right_target] += plusmax
  else:
    # 負の数の最大値のほうが大きい場合は左端に足す
    ans += [(minusmax_i + 1, left_target)]
    A[left_target - 1] += minusmax
    
if len(ans) > 2 * N:
  p = 1 / 0
print(len(ans))
for a in ans:
  print(*a)