Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math


N, K = map(int, input().split())

ans = math.floar(1 + math.log(N)/math.log(K))
print(ans)

Fixed submission:
N, K = map(int, input().split())

digit = 0
k = K
while N:
  r = N % k
  N -= r
  k *= K
  digit += 1

print(digit)
Buggy python submission (verdict: Runtime Error):
r1, c1, r2, c2 = map(int, input().split())

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**6+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def memo_comb(n, r, mod=MOD):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

def g(r, c):
  res = 0
  for i in range(r+1):
    res += memo_comb(i+c+1, i+1)
    res %= MOD
  
  return res

ans = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
ans %= MOD
print(ans)

Fixed submission:
r1, c1, r2, c2 = map(int, input().split())

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**6+2):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def memo_comb(n, r, mod=MOD):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

def g(r, c):
  res = 0
  for i in range(r+1):
    res += memo_comb(i+c+1, i+1)
    res %= MOD
  
  return res

ans = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

H, N = map(int, input().split())

AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append([A, B])

dp = [float('inf')]*(H+1)
dp[0] = 0
for h in range(1, H+1):
  for a, b in AB:
    if h - a <= 0:
      cost = b
    else:
      cost = dp[h-a] + b
    dp[h] = min(dp[h], cost)

print(dp[H])

Fixed submission:
import bisect

H, N = map(int, input().split())

AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append([A, B])

dp = [float('inf')]*(H+1)
dp[0] = 0
for h in range(1, H+1):
  for a, b in AB:
    if h - a <= 0:
      cost = b
    else:
      cost = dp[h-a] + b
    dp[h] = min(dp[h], cost)

print(dp[H])
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

LR = []
for i in range(N):
  X, L = map(int, input().split())
  LR.append([X-L, 1, i])
  LR.append([X+L, 0, i])

LR.sort()

tree = np.eye(N, dtype=bool)



Fixed submission:
N = int(input())

RL = []
for i in range(N):
  x, l = map(int, input().split())
  RL.append([x+l, x-l])

RL.sort()
right = -10**9

ans = 0
for r, l in RL:
  if l >= right:
    right = r
    ans += 1
    
print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

LR = []
for i in range(N):
  X, L = map(int, input().split())
  LR.append([X-L, 1, i])
  LR.append([X+L, 0, i])

LR.sort()

tree = np.eye(N, dtype=bool)

is_now = np.zeros(N, dtype=bool)
for y, lr, idx in LR:
  if lr == 1:
    is_now[idx] = True
    tree[idx] += is_now
  else:
    is_now[idx] = False

tree += tree.T

a = np.sum(tree)
B = np.argsort(tree.sum(axis=0))[::-1]



Fixed submission:
N = int(input())

RL = []
for i in range(N):
  x, l = map(int, input().split())
  RL.append([x+l, x-l])

RL.sort()
right = -10**9

ans = 0
for r, l in RL:
  if l >= right:
    right = r
    ans += 1
    
print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

LR = []
for i in range(N):
  X, L = map(int, input().split())
  LR.append([X-L, 1, i])
  LR.append([X+L, 0, i])

LR.sort()

tree = np.eye(N, dtype=bool)

is_now = np.zeros(N, dtype=bool)
for y, lr, idx in LR:
  if lr == 1:
    is_now[idx] = True
    tree[idx] += is_now
  else:
    is_now[idx] = False

tree += tree.T

a = np.sum(tree)
B = np.argsort(tree.sum(axis=0))[::-1]

for i, b in enumerate(B):
  if a == N:
    break
  tree[b] = tree[:, b] = False
  tree[b, b] = True
  a = np.sum(tree)

print(N - i)

Fixed submission:
N = int(input())

RL = []
for i in range(N):
  x, l = map(int, input().split())
  RL.append([x+l, x-l])

RL.sort()
right = -10**9

ans = 0
for r, l in RL:
  if l >= right:
    right = r
    ans += 1
    
print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

LR = []
for i in range(N):
  X, L = map(int, input().split())
  LR.append([X-L, 1, i])
  LR.append([X+L, 0, i])

LR.sort()

tree = np.zeros([N, N], dtype=bool)

is_now = np.zeros(N, dtype=bool)
for y, lr, idx in LR:
  if lr == 1:
    is_now[idx] = True
    tree[idx] += is_now
  else:
    is_now[idx] = False
    tree[idx] += is_now


tree += tree.T

a = np.sum(tree, axis=0)
while (a != 1).any():
  idx = a.argmax()
  tree = np.delete(np.delete(tree, idx, 0), 1)
  a = np.sum(tree, axis=0)

print(len(tree))

Fixed submission:
N = int(input())

RL = []
for i in range(N):
  x, l = map(int, input().split())
  RL.append([x+l, x-l])

RL.sort()
right = -10**9

ans = 0
for r, l in RL:
  if l >= right:
    right = r
    ans += 1
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

def calc_intersection(z1, z2, R):
  d = np.linalg.norm(z1 - z2)
  if R < d/2:
    return None
  else:
    m = (z1 + z2) / 2
    v = np.sqrt(R**2/d**2 - 0.25) * np.array([z2[1]-z1[1], z1[0]-z2[0]])
    return np.r_[(m+v)[None, :], (m-v)[None, :]]


def check(R):
  intersections = np.empty([0, 2])
  for i in range(N):
    for j in range(i+1, N):
      points = calc_intersection(xy[i], xy[j], R)
      if points is None:
        return False
      else:
        intersections = np.r_[intersections, points]
  D = np.linalg.norm(intersections[None,:] - xy[:,None], axis=2)
  if (D <= R).prod(axis=0).any():
    return True
  else:
    return False


N = int(input())
xy = []
for i in range(N):
  xy.append(list(map(int, input().split())))

xy = np.array(xy)
left = 0 # False
right = 500 * 2**0.5 # True
while right - left > 0.000001:
  mid = (left + right) / 2
  if check(mid):
    right = mid
  else:
    left = mid

print(right)

Fixed submission:
def calc_intersection(z1, z2, R):
  d2 = (z1[0]-z2[0])**2 + (z1[1]-z2[1])**2
  d = d2 ** 0.5
  if R < d/2:
    return None
  else:
    m = [(z1[0]+z2[0])*0.5, (z1[1]+z2[1])*0.5]
    l = (R**2/d2 - 0.25)**0.5
    v = [l*(z2[1]-z1[1]), l*(z1[0]-z2[0])]
    return [[m[0]+v[0], m[1]+v[1]], [m[0]-v[0], m[1]-v[1]]]


def check(R):
  intersections = []
  for i in range(N):
    for j in range(i+1, N):
      points = calc_intersection(xy[i], xy[j], R)
      if points is None:
        return False
      else:
        intersections.extend(points)
  
  for px, py in intersections:
    res = True
    for x, y in xy:
      res *= ((x-px)**2 + (y-py)**2 <= R**2+0.000001)
      if not res:
        break
    if res:
      return True
  return False


N = int(input())
xy = [list(map(int, input().split())) for i in range(N)]
left = 0 # False
right = 500 * 2**0.5 # True
while right - left > 0.000001:
  mid = (left + right) / 2
  if check(mid):
    right = mid
  else:
    left = mid

print(right)
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = list(map(int, input().split()))
d = [dj - di for di, dj in zip(X, X[1:])][::-1]

MOD = 10**9 + 7
count_d = [[0] * (N) for i in range(N-1)]
count_d[0][1] = 1

fac = 1
for n in range(1, N-1):
  fac = fac*n % MOD
  for i in range(1, n+2):
    count_d[n][i] = ((n+1-i+1)*count_d[n-1][i] + (i-1)*count_d[n-1][i-1] + fac)%MOD

ans = 0
for di, ci in zip(d, count_d[-1][1:]):
  ans += di*ci % MOD
  ans %= MOD

print(ans)

Fixed submission:
MOD = 10**9 + 7
N = int(input())
X = list(map(int, input().split()))
D = [dj - di for di, dj in zip(X, X[1:])]

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def framod(n, a=1, mod=10**9+7):
    for i in range(1,n+1):
        a = a * i % mod
    return a

count_d = []
frac_Nm1 = framod(N-1)
for i in range(1, N):
  count_d.append(frac_Nm1 * power(i, MOD-2) % MOD)

for i in range(1, N-1):
  count_d[i] += count_d[i-1]


ans = sum([d*c % MOD for d, c in zip(D, count_d)]) % MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

Ap = A[-P] # 初期状態でP番目に大きい点数
idx = bisect.bisect_left(A, Ap) # 初期状態で得点がApより小さい問題の数
ans = N - idx # 初期状態で得点がAp以上であれば候補に入る


for i, a in enumerate(A[:idx]):
  j = 1
  b = a + M
  if b < Ap:
    continue
  n0 = bisect.bisect_right(A, a) # M人全員から投票されてもbを超えない問題の数
  n1 = N - bisect.bisect_left(A, b+1) # 投票されない状態で既にbより点数が高い問題の数
  mv = (V - n0) * M # 上の問題達には取り敢えず投票しておいて、他に選べる問題の数
  if mv <= 0:
    j = 0
    break
  else:
    res = False
    p = P - 1
    for _a in A[n0:][::-1]:
      if p:
        p -= 1
        diff = M
      else:
        diff = b - _a
      if diff <= 0:
        break
      else:
        mv -= diff
        if mv <= 0:
          res = True
          j = 0
          break
    if res:
      break

ans += idx - i - j # 一度候補に入る数を発見したら、それ以降も当然候補に入る
print(ans)

Fixed submission:
import bisect

N, M, V, P = map(int, input().split())
A = list(map(int, input().split())) + [-M-1]
A.sort()

Ap = A[-P] # 初期状態でP番目に大きい点数
I = N + 2 - P
right = N + 1 - P
left = 0

while left + 1 < right:
  mid = (left + right) // 2
  b = A[mid] + M
  if b < Ap:
    left = mid
  else:
    v = V - (bisect.bisect_right(A, A[mid])-1) - (P-1)
    if v <= 0:
      right = mid
    else:
      mv = M*v
      for i in range(mid+1, I):
        if A[i] == A[mid]:
          continue
        mv -= b - A[i]
        if mv <= 0:
          break
      if mv <= 0:
        right = mid
      else:
        left = mid

print(N + 1 - right)
Buggy python submission (verdict: Runtime Error):
import numpy as np
 
mod = 10**9 + 7
N = input()
A = np.array(list(map(int, input().split())))
A = np.atleast_2d(A)

print((np.sum((A ^ A.T) % mod) % mod) // 2)

Fixed submission:
import numpy as np
 
mod = 10**9 + 7
max_digit = 60
N = int(input())
A = np.array(list(map(int, input().split())))

result = 0
base = 1
for _ in range(max_digit + 1):
  a = A % 2
  c = np.count_nonzero(a == 0)
  result = (result + (base*(N - c)*c) % mod) % mod
  A = A >> 1
  base *= 2

print(result)

Buggy python submission (verdict: Runtime Error):
import numpy as np
 
mod = 10**9 + 7
N = input()
A = np.array(list(map(int, input().split())), dtype='uint64') % mod
A = np.atleast_2d(A)

print((np.sum((A ^ A.T) % mod) % mod) // 2)

Fixed submission:
import numpy as np
 
mod = 10**9 + 7
max_digit = 60
N = int(input())
A = np.array(list(map(int, input().split())))

result = 0
base = 1
for _ in range(max_digit + 1):
  a = A % 2
  c = np.count_nonzero(a == 0)
  result = (result + (base*(N - c)*c) % mod) % mod
  A = A >> 1
  base *= 2

print(result)

Buggy python submission (verdict: Runtime Error):
import numpy as np

mod = 10**9 + 7
N = input()
A = np.atleast_2d(list(map(int, input().split()))) % mod

print((np.sum((A ^ A.T) % mod) % mod) // 2)

Fixed submission:
import numpy as np
 
mod = 10**9 + 7
max_digit = 60
N = int(input())
A = np.array(list(map(int, input().split())))

result = 0
base = 1
for _ in range(max_digit + 1):
  a = A % 2
  c = np.count_nonzero(a == 0)
  result = (result + (base*(N - c)*c) % mod) % mod
  A = A >> 1
  base *= 2

print(result)
Buggy python submission (verdict: Runtime Error):
X = int(input().split())

dp = [False] * (X + 1)
dp[0] = True
for i in range(X):
  if i:
    for x in [100, 101, 102, 103, 104, 105]:
      if i+x <= X:
        dp[i+x] = True

if dp[-1]:
  print(1)
else:
  print(0)

Fixed submission:
X = int(input())

dp = [False] * (X + 1)
dp[0] = True
for i in range(X):
  if dp[i]:
    for x in [100, 101, 102, 103, 104, 105]:
      if i+x <= X:
        dp[i+x] = True

if dp[-1]:
  print(1)
else:
  print(0)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

ans = 1
num_color = [-1, -1, -1]
for a in A:
  ans = (ans * num_color.count(a-1)) % MOD
  num_color[num_color.index(a-1)] = a

print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

ans = 1
num_color = [-1, -1, -1]
for a in A:
  ans = (ans * num_color.count(a-1)) % MOD
  try:
    num_color[num_color.index(a-1)] = a
  except:
    print(0)
    quit()

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
count = [0 for i in range(N)]
n = []
for _ in range(N-1):
  a, b = map(int, input().split())
  count[a-1] += 1
  count[b-1] += 1
  n.append([a, b])

K = max(count)
All = set(range(1, K+1))
memo = [[] for i in range(N)]
print(K)
for a, b in n:
  m = list(All - set(memo[a-1] + memo[b-1]))[0]
  memo[a-1].append(m)
  memo[b-1].append(m)
  print(m)

Fixed submission:
from collections import deque

N = int(input())

G = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  G[a-1].append([b-1, i])
  G[b-1].append([a-1, i])


q = deque()
q.append([0, 0, 0])

colors = [0] * (N-1)
while q:
  node, parent, edge_color = q.popleft()
  c = 1
  for child, index in G[node]:
    if child == parent:
      continue
    
    if c == edge_color:
      c += 1
    
    q.append([child, node, c])
    colors[index] = c
    c += 1

print(max(colors))
print(*colors, sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

A = set([i for i in range(1, 10**5)])
s = [[] for _ in range(N)]
r = []
for _ in range(N-1):
  a, b = map(int, input().split())
  n = min(A - set(s[a-1] + s[b-1]))
  s[a-1] += [n]
  s[b-1] += [n]
  r.append(n)

print(max(r))
print(*r, sep='\n')

Fixed submission:
from collections import deque

N = int(input())

G = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  G[a-1].append([b-1, i])
  G[b-1].append([a-1, i])


q = deque()
q.append([0, 0, 0])

colors = [0] * (N-1)
while q:
  node, parent, edge_color = q.popleft()
  c = 1
  for child, index in G[node]:
    if child == parent:
      continue
    
    if c == edge_color:
      c += 1
    
    q.append([child, node, c])
    colors[index] = c
    c += 1

print(max(colors))
print(*colors, sep='\n')

Buggy python submission (verdict: Runtime Error):
N = int(input())
count = [0 for i in range(N)]
n = []
for _ in range(N-1):
  a, b = map(int, input().split())
  count[a-1] += 1
  count[b-1] += 1
  n.append([a, b])

K = max(count)
All = set([j for j in range(1, K+1)])
memo = [[] for i in range(N)]
print(K)
for i in range(N-1):
  a, b = n[i]
  m = list(All - set(memo[a-1] + memo[b-1]))[0]
  memo[a-1].append(m)
  memo[b-1].append(m)
  print(m)


Fixed submission:
from collections import deque

N = int(input())

G = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  G[a-1].append([b-1, i])
  G[b-1].append([a-1, i])


q = deque()
q.append([0, 0, 0])

colors = [0] * (N-1)
while q:
  node, parent, edge_color = q.popleft()
  c = 1
  for child, index in G[node]:
    if child == parent:
      continue
    
    if c == edge_color:
      c += 1
    
    q.append([child, node, c])
    colors[index] = c
    c += 1

print(max(colors))
print(*colors, sep='\n')
Buggy python submission (verdict: Time Limit Exceeded):
M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = []
ids = []
for i, a in enumerate(A):
  ids.append(i+1)
  accum = list(map(lambda x:x+a, accum))
  accum.append(a)
  ans += sum([1 if s%K == idx else 0 for s, idx in zip(accum, ids[::-1])])

print(ans)  

Fixed submission:
M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = [0]
d = {0 : 1}

for i, a in enumerate(A):
  accum.append((accum[-1] + a - 1)%K)
  if i >= K - 1:
    d[accum[i-K+1]] -= 1
  
  if accum[-1] in d:
    ans += d[accum[-1]]
    d[accum[-1]] += 1
  
  else:
    d[accum[-1]] = 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = []
ids = []
for i, a in enumerate(A):
  ids.append(i+1)
  accum = list(map(lambda x:x+a, accum))
  accum.append(a)
  ans += sum([1 if s%K == idx else 0 for s, idx in zip(accum, ids[::-1])])

print(ans)  

Fixed submission:
M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = [0]
d = {0 : 1}

for i, a in enumerate(A):
  accum.append((accum[-1] + a - 1)%K)
  if i >= K - 1:
    d[accum[i-K+1]] -= 1
  
  if accum[-1] in d:
    ans += d[accum[-1]]
    d[accum[-1]] += 1
  
  else:
    d[accum[-1]] = 1

print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np

M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = np.array([], dtype=int)
for i, a in enumerate(A):
  accum += a
  accum = np.r_[accum, a]
  ans += sum((accum % K) == np.arange(i+1, 0, -1))

print(ans)

Fixed submission:
M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = [0]
d = {0 : 1}

for i, a in enumerate(A):
  accum.append((accum[-1] + a - 1)%K)
  if i >= K - 1:
    d[accum[i-K+1]] -= 1
  
  if accum[-1] in d:
    ans += d[accum[-1]]
    d[accum[-1]] += 1
  
  else:
    d[accum[-1]] = 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = np.array([], dtype=int)
for i, a in enumerate(A):
  accum += a
  accum = np.r_[accum, a]
  ans += sum((accum % K) == np.arange(i+1, 0, -1))

print(ans)  

Fixed submission:
M, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
accum = [0]
d = {0 : 1}

for i, a in enumerate(A):
  accum.append((accum[-1] + a - 1)%K)
  if i >= K - 1:
    d[accum[i-K+1]] -= 1
  
  if accum[-1] in d:
    ans += d[accum[-1]]
    d[accum[-1]] += 1
  
  else:
    d[accum[-1]] = 1

print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = input()

steps = [[] for i in range(N)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if root[N] == -1:
  ans = -1
else:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)

Fixed submission:
N, M = map(int, input().split())
S = input()

steps = [[] for i in range(N+1)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if root[N] == -1:
  ans = -1
else:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = input()

steps = [[] for i in range(N)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    ans = -1
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if pos == N+1:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)

Fixed submission:
N, M = map(int, input().split())
S = input()

steps = [[] for i in range(N+1)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if root[N] == -1:
  ans = -1
else:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)
Buggy python submission (verdict: Runtime Error):
X, Y = map(int, input().split())
price = [0, 300000, 200000, 100000]
ans = price[X] + price[Y] + 400000*(X == Y == 1)

print(ans)

Fixed submission:
X, Y = map(int, input().split())
price = [0, 300000, 200000, 100000] + [0]*300
ans = price[X] + price[Y] + 400000*(X == Y == 1)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, T = map(int, input().split())
AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append([A, B])

AB.sort()

dp = [[0 for t in range(T)] for i in range(N+1)]

ans = 0
for i, ab in enumerate(AB):
  ans = max(ans, dp[i][T-1] + ab[1])
  for t in range(T):
    if t < ab[0]:
      dp[i+1][t] = dp[i][t]
    else:
      dp[i+1][t] = max(dp[i][t-ab[0]] + ab[1], dp[i][t])

print(ans)

Fixed submission:
N, T = map(int, input().split())
AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append([A, B])

AB.sort()

dp = [[0 for t in range(T)] for i in range(N+1)]

ans = 0
for i, ab in enumerate(AB):
  ans = max(ans, dp[i][T-1] + ab[1])
  for t in range(T):
    if t < ab[0]:
      dp[i+1][t] = dp[i][t]
    else:
      dp[i+1][t] = max(dp[i][t-ab[0]] + ab[1], dp[i][t])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = [0] + list(map(int, input().split()))

INF = 10**12
dp = [[INF] * (N+1) for i in range(N+1)]
dp[0][0] = 0

for x in range(1, N+1):
  dp[x][0] = 0
  dp[x][1] = H[x]
  for y in range(2, x+1):
    for i in range(x):
      dp[x][y] = min(dp[x][y], dp[i][y-1]+max(0, H[x]-H[i]))

ans = INF
for i in range(N+1):
  ans = min(ans, dp[i][N-K])

print(ans)

Fixed submission:
N, K = map(int, input().split())
H = [0] + list(map(int, input().split()))

INF = 10**12
dp = [[INF] * (N+1) for i in range(N+1)]
dp[0][0] = 0

for x in range(1, N+1):
  dp[x][0] = 0
  dp[x][1] = H[x]
  for y in range(2, x+1):
    for i in range(x):
      dp[x][y] = min(dp[x][y], dp[i][y-1]+max(0, H[x]-H[i]))

ans = INF
for i in range(N+1):
  ans = min(ans, dp[i][N-K])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
F = list(map(int, input().split()))
F.sort()
F = F[::-1]

def check(x, a=A, f=F, k=K):
  S = sum([max(ai - x//fi, 0) for ai, fi in zip(a, f)])
  if S > k:
    result = False
  else:
    result = True
  
  return result


l, r = 0, 10**12
m = (l + r) // 2

while True:
  result = check(m)
  if result:
    r = m
  else:
    l = m
  
  m = (l + r) // 2
  if r == l + 1:
    if check(l):
      x = l
    else:
      x = r
    break

print(x)

Fixed submission:
import numpy as np

N, K = map(int, input().split())
A = np.sort(list(map(int, input().split())))
F = np.sort(list(map(int, input().split())))[::-1]

l, r = 0, 10**12
m = (l + r) // 2

while True:
  if np.maximum(A - m//F, 0).sum() <= K:
    r = m
  else:
    l = m
  
  m = (l + r) // 2
  if r == l + 1:
    if np.maximum(A - l//F, 0).sum() <= K:
      x = l
    else:
      x = r
    break

print(x)