Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

def main():
    A, B, Q = map(int, input().split())
    s = list(int(input()) for _ in range(A))
    t = list(int(input()) for _ in range(B))

    sort_s = sorted(s)
    sort_t = sorted(t)
    for _ in range(Q):
        x = int(input())
        s_near = bisect.bisect_left(sort_s, x)
        t_near = bisect.bisect_left(sort_t, x)

        s_candidate = []
        t_candidate = []

        if s_near == 0:
            s_candidate.append(sort_s[s_near])
        elif s_near == A:
            s_candidate.append(sort_s[s_near-1])
        else:
            s_candidate.append(sort_s[s_near])
            s_candidate.append(sort_s[s_near-1])
        
        if t_near == 0:
            t_candidate.append(sort_t[t_near])
        elif t_near == B:
            t_candidate.append(sort_t[t_near-1])
        else:
            t_candidate.append(sort_t[t_near])
            t_candidate.append(sort_t[t_near-1])

        ans = float('inf')
        # sを先に訪れるパターンを考える
        for i in s_candidate:
            for j in t_candidate:
                tmp = abs(x - i) + abs(i - j)
                ans = min(ans, tmp)

        # tをさきに訪れるパターンを考える
        for k in t_candidate:
            for l in s_candidate:
                tmp = abs(x - k) + abs(k - l)
                ans = min(ans, tmp)

        print(ans)
        
main()

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

def main():
    A, B, Q = map(int, input().split())
    s = list(int(input()) for _ in range(A))
    t = list(int(input()) for _ in range(B))

    sort_s = sorted(s)
    sort_t = sorted(t)
    for _ in range(Q):
        x = int(input())
        s_near = bisect.bisect_left(sort_s, x)
        t_near = bisect.bisect_left(sort_t, x)

        s_candidate = []
        t_candidate = []

        if s_near == 0:
            s_candidate.append(sort_s[s_near])
        elif s_near == A:
            s_candidate.append(sort_s[s_near-1])
        else:
            s_candidate.append(sort_s[s_near])
            s_candidate.append(sort_s[s_near-1])
        
        if t_near == 0:
            t_candidate.append(sort_t[t_near])
        elif t_near == B:
            t_candidate.append(sort_t[t_near-1])
        else:
            t_candidate.append(sort_t[t_near])
            t_candidate.append(sort_t[t_near-1])

        ans = float('inf')
        # sを先に訪れるパターンを考える
        for i in s_candidate:
            for j in t_candidate:
                tmp = abs(x - i) + abs(i - j)
                ans = min(ans, tmp)

        # tをさきに訪れるパターンを考える
        for k in t_candidate:
            for l in s_candidate:
                tmp = abs(x - k) + abs(k - l)
                ans = min(ans, tmp)

        print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    match = [0,2,5,5,4,5,6,3,7,6]
    dp = [-1] * (N + 10)
    dp[0] = 0
    for i in range(N):
        if dp[i] != -1:
            for a in A:
                tmp = str(dp[i]) + str(a)
                dp[i+match[a]] = max(dp[i+match[a]], int(tmp))
        
    print(dp[N])


if __name__ == "__main__":
    main()

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

    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

    dp = [-1] * (N + 10)
    dp[0] = 0
    sort_A = sorted(A, reverse=True)

    for a in sort_A:
        tmp = cost[a]
        for i in range(N + 1):
            if dp[i] == -1:
                continue
            dp[i+tmp] = max(dp[i+tmp], dp[i] * 10 + a)

    print(dp[N])






main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = [0] * N
    B = [0] * N
    C = []
    for i in range(N):
        A[i], B[i] = map(int, input().split())
        C.append([A+B, i])

    C.sort(reverse=True)
    ans = 0
    for i, c in enumerate(C):
        if i % 2 == 0:
            ans += A[c[1]]
        else:
            ans -= B[c[1]]

    print(ans) 

    
    



if __name__ == "__main__":
    main()

Fixed submission:
def main():
    N = int(input())
    A = [0] * N
    B = [0] * N
    C = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
        C[i] = A[i] + B[i]

    C.sort(reverse=True)
    ans = -sum(B)
    for i, c in enumerate(C):
        if i % 2 == 0:
            ans += C[i]
    
    print(ans) 

    
    



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    d = defaultdict(list)
    for _ in range(N):
        t, v = map(int, input().split())
        d[t].append(v)

    other = []
    vmax = []
    for nums in d.values():
        vmax.append(max(nums))
        for j in nums:
            if j != max(nums):
                other.append(j)

    vmax.sort(reverse=True)
    other.sort(reverse=True)
    sum_v = list(accumulate(vmax))
    sum_o = list(accumulate(other))
    ans = 0
    for i in range(min(len(d), K)):
        tmp = (i + 1) * (i + 1) + sum_v[i]
        if K - (i + 1) > 0:
            tmp += sum_o[min(K-(i+1),len(sum_o))-1]
        ans = max(ans, tmp)

    print(ans)

    
    




if __name__ == "__main__":
    main()

Fixed submission:
import heapq

def main():
    N, K = map(int, input().split())
    sushi_list = []
    for _ in range(N):
        t, d = map(int, input().split())
        sushi_list.append((d,t))
    sushi_list = sorted(sushi_list, reverse=True)

    # 各種類(最大でK種類目まで)でおいしさが最大のものを保存
    keep = []
    # 取り替えるようのheapq
    exchange = []
    # keepに入っている種類
    types = set()
    for i in range(K):
        d, t = sushi_list[i]
        if t not in types:
            keep.append(d)
            types.add(t)
        else:
            heapq.heappush(exchange, d)

    base_point1 = sum(keep)
    base_point2 = sum(exchange)
    bonus_point = len(types)

    ans = base_point1 + base_point2 + bonus_point ** 2
    
    # K～N番目までをみて、選んでいない種類で最大のものを交換していく
    for i in range(K, N):
        if len(exchange) == 0:
            break

        d, t = sushi_list[i]
        # すでに選んだ種類のものはスキップする
        if t in types:
            continue 
        types.add(t)
        # 選んでいない種類で最大のものを追加する
        base_point1 += d
        # 選んだ種類で最小のものを削除する
        base_point2 -= heapq.heappop(exchange)
        bonus_point += 1
        ans = max(ans, base_point1 + base_point2 + bonus_point ** 2)

    print(ans)


    

main()
Buggy python submission (verdict: Runtime Error):
10 587586158 185430194
894597290 708587790
680395892 306946994
590262034 785368612
922328576 106880540
847058850 326169610
936315062 193149191
702035777 223363392
11672949 146832978
779291680 334178158
615808191 701464268

Fixed submission:
N, H, W = map(int, input().split(" "))
count = 0
for i in range(N):
        A, B = map(int, input().split(" "))
        if A // H > 0 and B // W > 0:
                count += 1

print(count)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split(" "))

h = [int(input()) for i in range(N)]

sort_h = sorted(h)
diff_h = 0
ans = []
for i in range(K):
    diff_h = sort_h[i+(K-1)] - sort_h[i] 
    ans.append(diff_h)

print(min(ans))

Fixed submission:

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

h = [int(input()) for i in range(N)]

sort_h = sorted(h)
diff_h = 0
ans = []
for i in range(len(h)-K+1):
    diff_h = sort_h[i+(K-1)] - sort_h[i] 
    ans.append(diff_h)

print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate, combinations

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    sum_A = sum(A)
    B = [0] + list(accumulate(A))
    cand = []
    for i in range(N+1):
        for j in range(i+1,N+1):
            cand.append(B[j] - B[i])
    cand.sort(reverse=True)
    length = len(bin(cand[K-1])[2:])
    num = []
    for c in cand:
        if len(bin(c)[2:]) < length:
            break
        num.append(c)

    ans = 0
    for item in combinations(num,K):
        n = 0
        for i in range(len(item)):
            if i == 0:
                n = item[i]
            n &= item[i]
        ans = max(ans, n)

    print(ans)




if __name__ == "__main__":
    main()

Fixed submission:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    sum_A = sum(A)
    B = [0] + list(accumulate(A))
    cand = []
    for i in range(N+1):
        for j in range(i+1,N+1):
            cand.append(B[j] - B[i])
    ans = 0
    for i in range(40):
        bit = 1 << (39 - i)
        cnt = 0
        new_cand = []
        for c in cand:
            if c & bit:
                cnt += 1
                new_cand.append(c)

        if cnt >= K:
            ans += 2 ** (39 - i)
            cand = new_cand


    print(ans)




if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    for i in range(M):
        if N + i > M:
            break
        if M % (N + i) == 0:
            print(M // (N + i))
            exit()


if __name__ == "__main__":
    main()

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def main():
    N, M = map(int, input().split())

    div = make_divisors(M)
    sort_div = sorted(div)

    ans = 0
    for a in sort_div:
        if a <= M // N:
            ans = a
        else:
            break

    print(ans)


main()
Buggy python submission (verdict: Runtime Error):
from operator import mul
from functools import reduce
from collections import Counter

def cmb(n, r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def prime_factor(n):
    ass = []
    for i in range(2, int(n ** 0.5) + 1):
        while n  % i == 0:
            ass.append(i)
            n = n // i
    if n != i:
        ass.append(n)
    return ass

def main():
    N, M = map(int, input().split())
    num_list = prime_factor(M)
    MOD = 10 ** 9 + 7
    C = Counter(num_list)
    ans = 1
    for i, j in C.items():
        if i == 1:
            continue
        ans *= cmb(j+N-1, j)
        ans %= MOD
    print(ans)



if __name__ == "__main__":
    main()

Fixed submission:
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    N, M = map(int, input().split())

    MOD = 10 ** 9 + 7
    c = collections.Counter(prime_factorize(M))
    ans = 1
    for i, j in c.items():
        ans *= cmb(N+j-1,N-1)
        ans %= MOD

    print(ans)

main()
Buggy python submission (verdict: Runtime Error):
def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    ans = []
    for h in range(H):
        for w in range(W-1):
            if A[h][w] % 2 == 1:
                A[h][w] -= 1
                A[h][w+1] += 1
                ans.append([h+1,w+1,h+1,w+2])

    for h in range(H-1):
        if A[h][W-1] % 2 == 1:
            A[h][W-1] -= 1
            A[h+1][W-1] += 1
            ans.append([h+1,w+1,h+2,w+1])

    print(len(ans))
    for a in ans:
        print(*a)



if __name__ == "__main__":
    main()

Fixed submission:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))

    ope = []

    for i in range(H-1):
        for j in range(W):
            if A[i][j] % 2 == 1:
                A[i][j] -= 1
                A[i+1][j] += 1
                ope.append([i+1,j+1,i+2,j+1])
    for j in range(W-1):
        if A[H-1][j] % 2 == 1:
            A[H-1][j] -= 1
            A[H-1][j+1] += 1
            ope.append([H,j+1,H,j+2])
            

    print(len(ope))
    for o in ope:
        print(*o) 

main()

Buggy python submission (verdict: Runtime Error):
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))

    ope = []

    for i in range(H):
        if i % 2 == 0:
            for j in range(W):
                if A[i][j] % 2 == 1:
                    if j != W - 1:
                        A[i][j] -= 1
                        A[i][j+1] += 1
                        ope.append([i+1,j+1,i+1,j+2])
                    elif i == H - 1 and j == W - 1:
                        continue
                    elif j == W - 1:
                        A[i][j] -= 1
                        A[i+1][j] += 1
                        ope.append([i+1,j+1,i+2,j+1])
        else:
            for j in range(W-1,-1,-1):
                if A[i][j] % 2 == 1:
                    if j != 0:
                        A[i][j] -= 1
                        A[i][j-1] += 1
                        ope.append([i+1,j+1,i+1,j])
                    elif i == 0 and j == 0:
                        continue    
                    elif j == 0:
                        A[i][j] -= 1
                        A[i+1][j] += 1
                        ope.append([i+1,j+1,i+2,j+1])

    print(len(ope))
    for o in ope:
        print(*o) 

main()

Fixed submission:
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))

    ope = []

    for i in range(H-1):
        for j in range(W):
            if A[i][j] % 2 == 1:
                A[i][j] -= 1
                A[i+1][j] += 1
                ope.append([i+1,j+1,i+2,j+1])
    for j in range(W-1):
        if A[H-1][j] % 2 == 1:
            A[H-1][j] -= 1
            A[H-1][j+1] += 1
            ope.append([H,j+1,H,j+2])
            

    print(len(ope))
    for o in ope:
        print(*o) 

main()
Buggy python submission (verdict: Runtime Error):
from statistics import median

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N

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

    b = int(median(B))
    sumB = 0
    for i in range(N):
        sumB += abs(B[i] - b)

    print(sumB)


main()

Fixed submission:
from statistics import median

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N

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

    b = int(median(B))
    sumB = 0
    for i in range(N):
        sumB += abs(B[i] - b)

    print(sumB)


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

    cnt = float('inf')
    for i in range(N):
        tmp = S[:i].count("W") + S[i+1:].count("E")
        if cnt > tmp:
            cnt = tmp

    print(cnt)

main()

Fixed submission:
N = int(input())
S = input()

ans = float('inf')
sum_E = [0]
sum_W = [0]
cnt_e = 0
cnt_w = 0

for i in range(N):
	if S[i] == 'E':
		cnt_e += 1
	else:
		cnt_w += 1
	sum_E.append(cnt_e)
	sum_W.append(cnt_w)

for i in range(N):
	ans = min(ans, sum_W[i] + sum_E[-1] - sum_E[i+1])

print(ans)

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

ans = float('inf')
for i in range(N):
    cnt = S[0:i].count('W') + S[i+1:].count('E')
    if ans > cnt:
        ans = cnt

print(ans)

Fixed submission:
N = int(input())
S = input()

ans = float('inf')
sum_E = [0]
sum_W = [0]
cnt_e = 0
cnt_w = 0

for i in range(N):
	if S[i] == 'E':
		cnt_e += 1
	else:
		cnt_w += 1
	sum_E.append(cnt_e)
	sum_W.append(cnt_w)

for i in range(N):
	ans = min(ans, sum_W[i] + sum_E[-1] - sum_E[i+1])

print(ans)
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

def main():
    @lru_cache(maxsize=1000)
    def dfs(d,R,sx,sy):
        if d == R:
            return 0
        x = 0
        y = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == d + D:
                    x = i
                    y = j
                    break
            else:
                continue
            break
        
        res = abs(x - sx) + abs(y - sy) + dfs(d+D,R,x,y)

        return res
    
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    Q = int(input())

    for _ in range(Q):
        L, R = map(int, input().split())
        sx = 0
        sy = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == L:
                    sx = i
                    sy = j
                    break
            else:
                continue
            break
        print(dfs(L,R,sx,sy))

        
        
        

main()

Fixed submission:
def main():
    H, W, D = map(int, input().split())
    field = [list(map(int, input().split())) for _ in range(H)]

    c = [0] * (H * W)
    for i in range(H):
        for j in range(W):
            c[field[i][j] - 1] = (i, j)
    
    d = [0] * (H * W)
    for l in range(H * W - D):
        i, j = c[l]
        x, y = c[l + D]
        d[l+D] = d[l] + abs(x - i) + abs(y - j)
    
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(d[R-1]-d[L-1])


main()

Buggy python submission (verdict: Runtime Error):
def main():
    def dfs(d,R,sx,sy):
        if d == R:
            return 0
        x = 0
        y = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == d + D:
                    x = i
                    y = j
                    break
            else:
                continue
            break
        
        res = abs(x - sx) + abs(y - sy) + dfs(d+D,R,x,y)

        return res
    
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    Q = int(input())

    for _ in range(Q):
        L, R = map(int, input().split())
        sx = 0
        sy = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == L:
                    sx = i
                    sy = j
                    break
            else:
                continue
            break
        print(dfs(L,R,sx,sy))

        
        
        

main()

Fixed submission:
def main():
    H, W, D = map(int, input().split())
    field = [list(map(int, input().split())) for _ in range(H)]

    c = [0] * (H * W)
    for i in range(H):
        for j in range(W):
            c[field[i][j] - 1] = (i, j)
    
    d = [0] * (H * W)
    for l in range(H * W - D):
        i, j = c[l]
        x, y = c[l + D]
        d[l+D] = d[l] + abs(x - i) + abs(y - j)
    
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(d[R-1]-d[L-1])


main()
Buggy python submission (verdict: Runtime Error):
from collections import deque

H,W = map(int, input().split())
s = [input() for _ in range(H)]

cnt = 0
for i in range(H):
    cnt += s[i].count('.')

dx = [1,0,-1,0]
dy = [0,1,0,-1]

visited = [[float('inf')] * W for i in range(H)]

def bfs():
    queue = deque([[0,0]])
    visited[0][0] = 1

    while queue:
        y,x = queue.popleft()

        if y == H - 1 and x == W - 1:
            return visited[y][x]
        
        for i in range(4):
            nx = x + dy[i]
            ny = y + dx[i]

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != '#' and visited[ny][nx] == float('inf'):
                queue.append([ny,nx])
                visited[ny][nx] = visited[y][x] + 1

print(cnt - bfs())

Fixed submission:
from collections import deque

H,W = map(int, input().split())
s = [input() for _ in range(H)]

cnt = 0
for i in range(H):
    cnt += s[i].count('.')

dx = [1,0,-1,0]
dy = [0,1,0,-1]

visited = [[float('inf')] * W for i in range(H)]

def bfs():
    queue = deque([[0,0]])
    visited[0][0] = 1

    while queue:
        y,x = queue.popleft()

        if y == H - 1 and x == W - 1:
            return visited[y][x]
        
        for i in range(4):
            nx = x + dy[i]
            ny = y + dx[i]

            if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != '#' and visited[ny][nx] == float('inf'):
                queue.append([ny,nx])
                visited[ny][nx] = visited[y][x] + 1
    
    return -1

num = bfs()

if num == -1:
    print(num)
else:
    print(cnt - num)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    d = [[-1] * N for _ in range(N)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        d[L][R] = D
        d[R][L] = D
        for i in range(N):
            if d[L][i] != -1 and d[i][R] != -1:
                if d[L][R] != d[L][i] + d[i][R]:
                    print('No')
                    exit()
    
    print('Yes')

if __name__ == "__main__":
    main()

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

class WeightUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

    # xの根を求める
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            px = self.find(self.parents[x])
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = px
            return px
    
    # xの根から距離
    def dist(self, x):
        self.find(x)
        return self.weight[x]

    # w[y] = w[x] + wとなるようにxとyを併合
    def unite(self, x, y, w):
        w += self.weight[x] - self.weight[y]
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            # sizeの大きいほうがx
            if self.parents[x] > self.parents[y]:
                x, y = y, x
                w = -w
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.weight[y] = w
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

    def diff(self, x, y):
        return self.dist(y) - self.dist(x)


    


def main():
    N, M = map(int, input().split())
    uni = WeightUnionFind(N)
    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        R -= 1
        if uni.same(L, R):
            if D != uni.diff(L, R):
                print('No')
                exit()
        else:
            uni.unite(L,R,D)

    print('Yes')
    


if __name__ == "__main__":
    main()