Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

H,W,M = map(int,input().split())

maze = [[0]*W for _ in range(H)]
for _ in range(M):
  h,w = map(int,input().split())
  h -= 1
  w -= 1
  maze[h][w] = 1

max_row = 0
rows = defaultdict(list)
for i in range(H):
  s = sum(maze[i])
  rows[s].append(i)
  max_row = max(max_row, s)

max_col = 0
cols = defaultdict(list)
for i in range(W):
  s = 0
  for j in range(H):
    s += maze[j][i]
  cols[s].append(i)
  max_col = max(max_col, s)

r_cans = rows[max_row]
c_cans = cols[max_col]

ans = 0
for r_can in r_cans:
  for c_can in c_cans:
    t = max_row + max_col
    if maze[r_can][c_can]: t -= 1
    ans = max(ans, t)

print(ans)

Fixed submission:
from collections import defaultdict

H,W,M = map(int,input().split())
dic = defaultdict(bool)
h_c = [ 0 for _ in range(H) ]
w_c = [ 0 for _ in range(W) ]

for _ in range(M):
  h,w = map(int,input().split())
  h -= 1
  w -= 1
  h_c[h] += 1
  w_c[w] += 1
  dic[(h,w)] = True

h_cans,w_cans = [],[]
h_max,w_max = max(h_c),max(w_c)
for i in range(H):
  if h_c[i] == h_max:
    h_cans.append(i)

for i in range(W):
  if w_c[i] == w_max:
    w_cans.append(i)

ans = h_max + w_max - 1
for h in h_cans:
  for w in w_cans:
    if not dic[(h,w)]: 
      print(ans+1)
      exit()

print(ans)
Buggy python submission (verdict: Runtime Error):
X,K,D = map(int,input().split())

m = X//D
if K >= m:
  if m%2 == K%2:
    print(abs(X%D))
  else:
    print(min(abs(X%D+D), abs(X%D-D)))
else:
  print( min( abs(X-D*K) , abs(X+D*K)

Fixed submission:
X,K,D = map(int,input().split())
X = abs(X)

if X - (D*K) >= 0:
  print(X-D*K)
else:
  k = K - (X//D)
  if k % 2 == 0:
    print(X%D)
  else:
    print(min(abs(X%D+D), abs(X%D-D)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))

g = [ [] for _ in range(N) ]
for i in range(N):
  g[i].append(P[i])

def dfs(i):
  global cycle
  nei = g[i][0]
  if nei in cycle: return
  cycle.append(nei)
  dfs(nei)

cycles = []

for i in range(N):
  cycle = []
  dfs(i)
  c = [ C[j] for j in cycle ]
  cycles.append(c) 

ans = -float('inf')
for i in range(N):
  c = cycles[i]
  cum = c[::]
  for j in range(1,len(c)):
    cum[j] = cum[j-1] + cum[j]

  if cum[-1] < 0:
    ans = max(ans, max(cum[0:K]))
  else:
    t = K//len(c)
    r = K - t*len(c)
    cum = [0]+cum[::]
    ans = max(ans, cum[-1]*t+max(cum[:r+1]))

print(ans)



Fixed submission:
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  tot = 0
  nex = i
  while True:
    nex = P[nex]
    cycle.append(C[nex])
    tot += C[nex]
    if nex == i: break

  l = len(cycle)
  t = 0
  for j in range(l):
    t += cycle[j]
    if j+1 > K: break
    now = t
    if tot > 0:
      now += tot*((K-(j+1))//l)
    ans = max(ans, now)

print(ans)

Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))

g = [ [] for _ in range(N) ]
for i in range(N):
  g[i].append(P[i])

def dfs(i):
  global cycle
  nei = g[i][0]
  if nei in cycle: return
  cycle.append(nei)
  dfs(nei)

cycles = []

for i in range(N):
  cycle = []
  dfs(i)
  c = [ C[j] for j in cycle ]
  cycles.append(c) 

ans = -float('inf')
for i in range(N):
  c = cycles[i]
  cum = c[::]
  for j in range(1,len(c)):
    cum[j] = cum[j-1] + cum[j]

  if cum[-1] < 0:
    ans = max(ans, max(cum[0:K]))
  else:
    t = K//len(c)
    r = K - t*len(c)
    cum = [0]+cum[::]
    ans = max(ans, cum[-1]*t+max(cum[:r+1]))

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  tot = 0
  nex = i
  while True:
    nex = P[nex]
    cycle.append(C[nex])
    tot += C[nex]
    if nex == i: break

  l = len(cycle)
  t = 0
  for j in range(l):
    t += cycle[j]
    if j+1 > K: break
    now = t
    if tot > 0:
      now += tot*((K-(j+1))//l)
    ans = max(ans, now)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = [1]+list(map(int,input().split()))
 
for i in range(1,N+1):
  A[i] = A[i-1]*A[i]
 
for i in range(K+1, N+1):
  prev = A[i-1] // A[i-K-1]
  now = A[i] // A[i-K]
  if now > prev:
    print('Yes')
  else:
    print("No")

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

for i in range(K, N):
  if A[i] > A[i-K]:
    print('Yes')
  else:
    print("No")

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int,input().split()))
prev = 1
for i in range(K):
  prev *= A[i]

for i in range(K+1, N+1):
  now = (prev // A[i-K-1])  * A[i-1]
  if now > prev:
    print('Yes')
  else:
    print("No")
  prev = now


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

for i in range(K, N):
  if A[i] > A[i-K]:
    print('Yes')
  else:
    print("No")

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

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

for i in range(K+1, N+1):
  prev = A[i-1] // A[i-K-1]
  now = A[i] // A[i-K]
  if now > prev:
    print('Yes')
  else:
    print("No")

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

for i in range(K, N):
  if A[i] > A[i-K]:
    print('Yes')
  else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
city = []
for i in range(N):
  x,y,p = map(int,input().split())
  city.append((x,y,p))

xx = [ [ abs(city[j][0]) for j in range(N) ] for i in range(2<<N) ]
yy = [ [ abs(city[j][1]) for j in range(N) ] for i in range(2<<N) ]

for i in range(2<<N):
  X = [0]
  rest = []
  for j in range(N):
    if i>>j&1:
      X.append(city[j][0])
      xx[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in X:
      res = min(res, abs(city[j][0]-k))
    xx[i][j] = res

for i in range(2<<N):
  Y = [0]
  rest = []
  for j in range(N):
    if i>>j&1:
      Y.append(city[j][1])
      yy[i][j] = 0
    else:
      rest.append(j)

  for j in rest:
    res = 10**15
    for k in Y:
      res = min(res, abs(city[j][1]-k))
    yy[i][j] = res


ans = [10**15 for _ in range(N+1)]
for i in range(2<<N):
  cond = i
  rest = [j for j in range(N) if i>>j&1==0]
  count = N-len(rest)

  while True:
    X = cond
    Y = i-cond
    temp = 0
    for j in rest:
      temp += min(xx[X][j], yy[Y][j])*city[j][2]
    ans[count] = min(ans[count], temp)
    if cond == 0:
      break
    else:
      cond = (cond-1)&i

for i in range(N+1):
  print(ans[i])


Fixed submission:
N=int(input())
city=[]
for i in range(N):
    x,y,p=map(int,input().split())
    city.append((x,y,p))
 
xx=[[abs(city[j][0]) for j in range(N)] for i in range(2**N)]
yy=[[abs(city[j][1]) for j in range(N)] for i in range(2**N)]
 
for i in range(2**N):
    X=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            X.append(city[j][0])
            xx[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in X:
            res=min(res,abs(city[j][0]-k))
        xx[i][j]=res
 
for i in range(2**N):
    Y=[0]
    rest=[]
    for j in range(N):
        if i>>j&1==1:
            Y.append(city[j][1])
            yy[i][j]=0
        else:
            rest.append(j)
    for j in rest:
        res=10**15
        for k in Y:
            res=min(res,abs(city[j][1]-k))
        yy[i][j]=res
 
ans=[10**15 for i in range(N+1)]
for i in range(2**N):
    cond=i
    rest=[j for j in range(N) if i>>j &1==0]
    count=N-len(rest)
    while True:
        X=cond
        Y=i-cond
        temp=0
        for j in rest:
            temp+=min(xx[X][j],yy[Y][j])*city[j][2]
        ans[count]=min(ans[count],temp)
        if cond==0:
            break
        else:
            cond=(cond-1)&i
 
for i in range(N+1):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))

res = 0
for i,a in enumerate(A):
  idx = i+1
  if idx%2==1 and a%2==1:
    res += 1

print(res

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

res = 0
for i,a in enumerate(A):
  idx = i+1
  if idx%2==1 and a%2==1:
    res += 1

print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())

i = n//1000
print(min(n%(1000*i), (1000*(i+1))%n))

Fixed submission:
n = int(input())

i = n%1000
if i != 0:
  print(1000-i)
else:
  print(i)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
N,K = map(int,input().split())
P = list(map(int,input().split()))

res = 10**16
for t in combinations(range(N), K):
  res = min(res, sum([P[i] for i in t]))
print(res)


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

print(sum(P[:K]))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)
lst = [1] * (10**6+1)
res = 0

for i,a in enumerate(A):
  if lst[a] == 0: continue
  if i==N-1 or A[i+1] != a:
    res += 1
  for j in range(a, 10**6+1, a):
    lst[j] = 0

print(res)

Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)
lst = [1] * (10**6+1)
res = 0

for i,a in enumerate(A):
  if lst[a] == 0: continue
  if i==N-1 or A[i+1] != a:
    res += 1
  for j in range(a, 10**6+1, a):
    lst[j] = 0

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

maze = []
maze.append(["@"]*(W+2))
for _ in range(H):
  row = list(input())
  maze.append(["@"]+row+["@"])
maze.append(["@"]*(W+2))

q = deque([(x1,y1)])
depth = 0
while q:
  for i,j in q:
    maze[i][j] = "@"

  new_q = deque([])
  l = len(q)
  for _ in range(l):
    x,y = q.pop()
    if (x,y) == (x2,y2):
      print(depth)
      exit()

    # Up
    for i in range(1, K+1):
      if maze[x-i][y] == "@": break
      new_q.append((x-i, y))

    # Down
    for i in range(1, K+1):
      if maze[x+i][y] == "@": break
      new_q.append((x+i, y))

    # Left
    for i in range(1, K+1):
      if maze[x][y-i] == "@": break
      new_q.append((x, y-i))

    # Right
    for i in range(1, K+1):
      if maze[x][y+i] == "@": break
      new_q.append((x, y+i))

  q = new_q
  depth += 1

print(-1)

Fixed submission:
from collections import deque
H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

maze = []
maze.append(["@"]*(W+2))
for _ in range(H):
  row = list(input())
  maze.append(["@"]+row+["@"])
maze.append(["@"]*(W+2))

q = deque([(x1,y1)])
depth = 0
while q:
  for i,j in q:
    maze[i][j] = "@"

  new_q = set()
  l = len(q)
  for _ in range(l):
    x,y = q.pop()
    if (x,y) == (x2,y2):
      print(depth)
      exit()

    # Up
    for i in range(1, K+1):
      if maze[x-i][y] == "@": break
      new_q.add((x-i, y))

    # Down
    for i in range(1, K+1):
      if maze[x+i][y] == "@": break
      new_q.add((x+i, y))

    # Left
    for i in range(1, K+1):
      if maze[x][y-i] == "@": break
      new_q.add((x, y-i))

    # Right
    for i in range(1, K+1):
      if maze[x][y+i] == "@": break
      new_q.add((x, y+i))

  q = deque(list(new_q))
  depth += 1

print(-1)
Buggy python submission (verdict: Runtime Error):
A,V = map(int,input().split())
B,W = map(int,input().split())
T = int(input())

A = A-B
B = 0

if A+V*T >= B+W*T:
  x = (B-A) / (V-W)
  print(x)
  if x <= T:
    print("YES")
  else:
    print("NO")
else:
  print("NO")


Fixed submission:
a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())
if v <= w:
  print("NO")
  exit()
d = abs(a-b)
if (v-w)*t >= d:
  print("YES")
else:
  print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
A = list(map(int, input().split()))

for _ in range(K):
  B = [0] * (N+1)
  for i in range(N):
    l = max(0, i-A[i])
    r = min(i+A[i]+1, N)
    B[l] += 1
    B[r] -= 1

  for i in range(N):
    B[i+1] += B[i]

  if B[:-1] == A: break
  A = B

for i in range(N):
  print(A[i])


Fixed submission:
from itertools import accumulate

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

for _ in range(K):
  arr = [0]*(N+1)
  for i, a in enumerate(A):
    left = max(0, i-a)
    right = min(N, i+a+1)
    arr[left] += 1
    arr[right] -= 1
  
  A = list(accumulate(arr[:-1]))
  if all(a == N for a in A):
    break

print(*A, sep=" ")

Buggy python submission (verdict: Time Limit Exceeded):
import math
N,K = map(int,input().split())
A = [-1]+list(map(int,input().split()))
B = [0] * (N+1)
B[0] = -1

for _ in range(K):
  for i,a in enumerate(A):
    if i==0: continue
    for j in range(max(math.ceil(i-a-0.5),0), min(math.floor(i+a+0.5),N)+1):
      B[j] += 1

  A = B[::]
  B = [0] * (N+1)

print(" ".join(map(str, A[1:])))

Fixed submission:
from itertools import accumulate

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

for _ in range(K):
  arr = [0]*(N+1)
  for i, a in enumerate(A):
    left = max(0, i-a)
    right = min(N, i+a+1)
    arr[left] += 1
    arr[right] -= 1
  
  A = list(accumulate(arr[:-1]))
  if all(a == N for a in A):
    break

print(*A, sep=" ")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int,input().split()))

res = 1
for e in A:
  res = res * e

if res > 10**18:
  print(-1)
else:
  print(res)

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

if 0 in A:
  print(0)
  exit()

res = 1
for e in A:
  res = res * e
  if res > 10**18:
    print(-1)
    exit()

print(res)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)
def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True 
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False

    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

def prime_factorization(n):
  d = 2
  cnt = 0
  seen = []
  while d*d <= n:
    if n%d == 0:
      t = 1
      while d**t <= n:
        if n % (d**t) == 0:
          seen.append(d**t)
          n //= (d**t)
          cnt += 1
          t += 1
        else:
          break
    d += 1
 
  if n != 1 and is_prime(n):
    cnt += 1
 
  return cnt
 
n = int(input())
print(prime_factorization(n))

Fixed submission:
import math
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(math.sqrt(n))+1):
    if temp%i == 0:
      cnt = 0
      while temp%i == 0:
        cnt += 1
        temp //= i
      arr.append([i, cnt])
  if temp != 1:
    arr.append([temp, 1])
  if arr == []:
    arr.append([n, 1])
  return arr

n = int(input())
factors = factorization(n)
res = 0
for j,cnt in factors:
  if j == 1: continue
  i = 1
  while cnt >= i:
    cnt -= i
    i += 1
    res += 1

print(res)

Buggy python submission (verdict: Runtime Error):
def is_prime(x):
    if x < 2: return False
    if x == 2 or x == 3 or x == 5: return True 
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False

    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

def prime_factorization(n):
  d = 2
  cnt = 0
  seen = []
  while d*d <= n:
    if n%d == 0:
      t = 1
      while d**t <= n:
        if n % (d**t) == 0:
          seen.append(d**t)
          n //= (d**t)
          cnt += 1
          t += 1
        else:
          break
    d += 1
 
  if n != 1 and is_prime(n):
    cnt += 1
 
  return cnt
 
n = int(input())
print(prime_factorization(n))


Fixed submission:
import math
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(math.sqrt(n))+1):
    if temp%i == 0:
      cnt = 0
      while temp%i == 0:
        cnt += 1
        temp //= i
      arr.append([i, cnt])
  if temp != 1:
    arr.append([temp, 1])
  if arr == []:
    arr.append([n, 1])
  return arr

n = int(input())
factors = factorization(n)
res = 0
for j,cnt in factors:
  if j == 1: continue
  i = 1
  while cnt >= i:
    cnt -= i
    i += 1
    res += 1

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
# N個のブロック、M色、K組
N,M,K = map(int,input().split())
MOD = 998244353

def nCr(n,r):
  mul, div = 1, 1
  for i in range(r):
    mul *= (n-i)
    div *= (i+1)
    mul %= MOD
    div %= MOD
  return mul * pow(div,MOD-2,MOD) % MOD

res = 0
for x in range(K+1):
  res += (M * pow(M-1, N-x-1, MOD)%MOD * nCr(N-1, x)%MOD)%MOD
  res %= MOD

print(res)

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

class Combination:
  def __init__(self, n_max, mod=998244353):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

comb = Combination(2*10**5)

res = 0
for x in range(K+1):
  res += (M * pow(M-1, N-x-1, MOD)%MOD * comb(N-1, x)%MOD)%MOD
  res %= MOD

print(res % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N,M,K = map(int,input().split())
MOD = 998244353

def nCr(n,r):
  ansMul, ansDiv = 1, 1
  for i in range(r):
    ansMul *= (n-i)
    ansDiv *= (i+1)
    ansMul %= MOD
    ansDiv %= MOD
  return (ansMul * pow(ansDiv, MOD-2, MOD)) % MOD

res = 0
for x in range(K, -1, -1):
  res += M*pow(M-1, N-x-1, MOD) * nCr(N-1, x)%MOD
  res %= MOD

print(res)

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

class Combination:
  def __init__(self, n_max, mod=998244353):
    self.mod = mod
    self.modinv = self.make_modinv_list(n_max)
    self.fac, self.facinv = self.make_factorial_list(n_max)

  def __call__(self, n, r):
    return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

  def make_factorial_list(self, n):
    # 階乗のリストと階乗のmod逆元のリストを返す O(n)
    # self.make_modinv_list()が先に実行されている必要がある
    fac = [1]
    facinv = [1]
    for i in range(1, n+1):
      fac.append(fac[i-1] * i % self.mod)
      facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
    return fac, facinv

  def make_modinv_list(self, n):
    # 0からnまでのmod逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
      modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
    return modinv

comb = Combination(2*10**5)

res = 0
for x in range(K+1):
  res += (M * pow(M-1, N-x-1, MOD)%MOD * comb(N-1, x)%MOD)%MOD
  res %= MOD

print(res % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import math
A,B,N = map(int,input().split())
res = 0

for x in range(1, B+1):
  res = max(res, math.floor(A*x/B)-A*math.floor(x/B))
  if x == N:
    print(res)
    exit()

print(res)

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

x = min(N, B-1)
print((A*x//B) - A*(x//B))
Buggy python submission (verdict: Runtime Error):
S = input()[::-1]
cur = 0
mods = Counter()
mods[0] += 1
MOD = 2019
for i,d in enumerate(S):
  cur += int(d) * pow(10, i, MOD)
  mods[cur%MOD] += 1

res = 0
for k,v in mods.items():
  res += (v * (v-1) // 2)

print(res)

Fixed submission:
from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
S = input()[::-1]
cur = 0
mods = Counter()
mods[0] += 1
for i,d in enumerate(S):
  cur += int(d) * 10**i
  mods[cur%2019] += 1

res = 0
for k,v in mods.items():
  res += (v * (v-1) // 2)

print(res)

Fixed submission:
from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
ans = 0
x = 1
# 累積和を格納
tot = 0
# 累積和のmod 2019をカウントする
cnt = [0] * 2019

for i in range(N)[::-1]:
  cnt[tot] += 1

  tot += int(S[i]) * x
  tot %= 2019
  ans += cnt[tot]
  x *= 10

print(ans)

Fixed submission:
from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)

Buggy python submission (verdict: Runtime Error):
S = "1817181712114"
N = len(S)
ans = 0
x = 1
# 累積和を格納
tot = 0
# 累積和のmod 2019をカウントする
cnt = [0] * 2019

for i in range(N)[::-1]:
  cnt[tot] += 1

  tot += int(S[i]) * x
  tot %= 2019
  if cnt[tot] > 0:
    import pdb; pdb.set_trace()
  ans += cnt[tot]
  x *= 10

print(ans)

Fixed submission:
from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
res = 0

for i in range(3, len(S)):
  last = S[i]
  for j in range(i-3):
    product = int(S[j:i+1])

    if product % 2019 == 0:
      res += 1

print(res)

Fixed submission:
from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd

K = int(input())
res = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      s = gcd(a,b)
      res += gcd(s,c)

print(res)

Fixed submission:
from math import gcd

K = int(input())
res = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      res += gcd(gcd(a,b),c)

print(res)