Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)


def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

def func(x):
    return x - 1
def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

def func(x):
    return x - 1
def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from decimal import Decimal

def main():
    N = int(input())
    A = [Decimal(input()) for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            tmp = '{:.20f}'.format(A[i] * A[j])
            if not '.' in tmp:
                cnt += 1
            else:
                a = tmp.split('.')[1]
                if len(a) == a.count('0'):
                    cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

Fixed submission:
from collections import Counter
from decimal import Decimal

def func(n):
    cnt2 = 0
    cnt5 = 0
    while n % 2 == 0:
        n //= 2
        cnt2 += 1
    while n % 5 == 0:
        n //= 5
        cnt5 += 1
    return cnt2, cnt5

def main():
    N = int(input())
    A = [input() for _ in range(N)]
    ctr = Counter()

    for a in A:
        d = Decimal(a)
        d = int(d * 1000000000)
        cnt2, cnt5 = func(d)
        ctr[(cnt2,cnt5)] += 1
    ans = 0
    for (ni1, go1), v1 in ctr.items():
        for (ni2, go2), v2 in ctr.items():
            if not (ni1 + ni2 >= 18 and go1 + go2 >= 18):
                continue
            if ni1 == ni2 and go1 == go2:
                ans += v1 * (v1 - 1)
            else:
                ans += v1 * v2


    print(ans // 2)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def divisor(n,A):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            if i in A:
                return False
            ass.append(i)
            if i**2 == n:
                continue
            if n//i in A:
                return False
    return True

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    cnt = 0
    for i in range(N):
        if i > 0 and A[i] == A[i-1]:
            continue
        if divisor(A[i],A[i+1:]):
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Fixed submission:
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    N = int(input())
    A = list(map(int, input().split()))
    max_A = max(A)
    ans = [0] * (max_A + 1)
    A.sort()
    for a in A:
        tmp = 1
        b = 0
        while b <= max_A:
            b = a * tmp
            if b > max_A:
                break
            ans[b] += 1
            tmp += 1
    cnt = 0
    for a in A:
        if ans[a] == 1:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    cnt = 0
    for i in range(N):
        if i > 0 and A[i] == A[i-1]:
            continue
        for j in range(i+1,N):
            if A[i] % A[j] == 0:
                break
        else:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Fixed submission:
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    N = int(input())
    A = list(map(int, input().split()))
    max_A = max(A)
    ans = [0] * (max_A + 1)
    A.sort()
    for a in A:
        tmp = 1
        b = 0
        while b <= max_A:
            b = a * tmp
            if b > max_A:
                break
            ans[b] += 1
            tmp += 1
    cnt = 0
    for a in A:
        if ans[a] == 1:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    T = input()
    ans = ''
    for t in T:
        if t == '?':
            ans += 'D'
        else:
            ans += t
    print(ans)




if __name__ == "__main__":
    main()

Fixed submission:
def main():
    T = input()
    print(T.replace('?','D'))



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    B = [0] * N
    for i in range(N):
        B[i] = (i + 1) - A[i]
        A[i] += i + 1

    d = defaultdict(int)
    C = []
    for i in range(N-1,-1,-1):
        d[B[i]] += 1
        C.append(d.copy())
    C.reverse()
    ans = 0
    for i in range(N-1):
        ans += C[i][A[i]]

    print(ans)

    


if __name__ == "__main__":
    main()

Fixed submission:
from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    B = [0] * N
    for i in range(N):
        B[i] = (i + 1) - A[i]
        A[i] += i + 1

    d = defaultdict(int)
    ans = 0
    for i in range(N-1,0,-1):
        d[B[i]] += 1
        ans += d[A[i-1]]

    print(ans)

    


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import sys
from itertools import accumulate

input = sys.stdin.readline

def main():
    X, Y, A, B, C = map(int, input().split())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    R = list(map(int, input().split()))
    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)
    P_acc = [0] + list(accumulate(P))
    Q_acc = [0] + list(accumulate(Q))
    R_acc = [0] + list(accumulate(R))
    ans = 0
    for i in range(X+1):
        tmp = 0
        red = i
        tmp += P_acc[red]
        if C < X - i:
            continue
        no_color = X - i
        tmp += R_acc[X-i]
        blue = Q_acc[Y]
        b_h = Q[:Y]
        heapq.heapify(b_h)
        for j in range(X-i,C):
            a = heapq.heappop(b_h)
            if R[j] > a:
                heapq.heappush(b_h, R[j])
                blue -= a
                blue += R[j]
            else:
                break
        tmp += blue
        ans = max(ans, tmp)

    print(ans)







if __name__ == "__main__":
    main()

Fixed submission:
import heapq
import sys
from itertools import accumulate
from collections import defaultdict

input = sys.stdin.readline

def main():
    X, Y, A, B, C = map(int, input().split())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    R = list(map(int, input().split()))
    ans = 0
    P_d = defaultdict(int)
    Q_d = defaultdict(int)
    R_d = defaultdict(int)

    for i in range(len(P)):
        P[i] = -P[i]
        P_d[P[i]] += 1
        
    for i in range(len(Q)):
        Q[i] = -Q[i]
        Q_d[Q[i]] += 1

    
    for i in range(len(R)):
        R[i] = -R[i]
        R_d[R[i]] += 1

    H = P + Q + R
    heapq.heapify(H)
    red = 0
    green = 0
    nocl = 0
    ans = 0
    for i in range(A + B + C):
        tmp = heapq.heappop(H)
        if red + green + nocl == X + Y:
            print(-ans)
            exit()

        if P_d[tmp] >= 1 and red < X:
            P_d[tmp] -= 1
            red += 1
            ans += tmp
        elif Q_d[tmp] >= 1 and green < Y:
            Q_d[tmp] -= 1
            green += 1
            ans += tmp
        elif R_d[tmp] >= 1:
            R_d[tmp] -= 1
            nocl += 1
            ans += tmp
    





if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

def main():
    N = int(input())
    d = defaultdict(int)
    for _ in range(N):
        S = input()
        d[S] += 1

    ans = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
    ans.sort()
    for a in ans:
        print(a)
    
    



if __name__ == "__main__":
    main()

Fixed submission:
from collections import defaultdict

def main():
    N = int(input())
    d = defaultdict(int)
    for _ in range(N):
        S = input()
        d[S] += 1

    max_d = max(d.values())
    ans = []
    for key, value in d.items():
        if value == max_d:
            ans.append(key)
    ans.sort()
    for a in ans:
        print(a)
    
    



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    A, B, K = map(int, input().split())
    C = max(A - K , 0)
    K = max(K - A , 0)
    D = max(B - K , 0)
    print(C, D)



if __name__ == "__main__":
    main()

Fixed submission:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def main():
    X = int(input())
    for i in range(X, 10**12):
        if is_prime(i):
            print(i)
            exit()




if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            C[h][w] = abs(A[h][w] - B[h][w])

    dp = [[[0] * (80 * 80) for _ in range(W)] for _ in range(H)]
    dh = [1,0]
    dw = [0,1]
    dp[0][0][C[0][0]] = 1
    for h in range(H):
        for w in range(W):
            for i in range(80*80):
                for j in range(2):
                    nh = h - dh[j]
                    nw = w - dw[j]
                    if 0 <= nh < H and 0 <= nw < W:
                        if abs(C[h][w] + i) < 6400:
                            dp[h][w][abs(C[h][w] + i)] |= dp[nh][nw][i]
                        if abs(C[h][w] - i) < 6400:
                            dp[h][w][abs(C[h][w] - i)] |= dp[nh][nw][i]
                    
    ans = float('inf')
    for i in range(80*80):
        if dp[H-1][W-1][i]:
            ans = min(i, ans)

    print(ans) 



if __name__ == "__main__":
    main()

Fixed submission:
def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            C[h][w] = abs(A[h][w] - B[h][w])

    dp = [[0 for _ in range(6400)] for _ in range(H*W)]
    dp[0][C[0][0]] = 1

    for d in range(H*W):
        h, w = divmod(d, W)
        for k in range(6400):
            if not dp[h*W+w][k]:
                continue
            nh, nw = h+1, w+1
            if nh < H:
                if k + C[nh][w] < 6400:
                    dp[nh*W+w][k+C[nh][w]] = 1
                dp[nh*W+w][abs(k-C[nh][w])] = 1
            if nw < W:
                if k + C[h][nw] < 6400:
                    dp[h*W+nw][k+C[h][nw]] = 1
                dp[h*W+nw][abs(k-C[h][nw])] = 1

    for k in range(6400):
        if dp[-1][k]:
            print(k)
            exit()

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque

def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                flag1 = False
                flag2 = False
                for n in range(N):
                    if S[n] == str(i) and not flag1 and not flag2:
                        flag1 = True
                        continue
                    if S[n] == str(j) and flag1 and not flag2:
                        flag2 = True
                        continue
                    if S[n] == str(k) and flag1 and flag2:
                        ans += 1
                        break


    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
from collections import defaultdict, deque

def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(1000):
        password = str(i).zfill(3)
        j = 0
        for s in S:
            if s == password[j]:
                j += 1
            if j == 3:
                ans += 1
                break

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import math
from decimal import *

def main():
    a, b, x = map(int, input().split())
    c = decimal(b) * decimal(b) * decimal(a)
    ans = math.degrees(math.atan(decimal(c)/decimal(x)))
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
from decimal import *
import math

def main():
    a, b, x = map(int, input().split())
    if a * a * b == x:
        print(0)
        exit()
    if Decimal(a) * Decimal(b) / Decimal(2) >= Decimal(x) / Decimal(a):
        tmp = Decimal(2) * Decimal(x) / (Decimal(a) * Decimal(b))
        c = math.atan(Decimal(tmp) / Decimal(b))
        d_deg = math.degrees(Decimal(c))
        print(Decimal(90) - Decimal(d_deg))
    else:
        d = (Decimal(2) * Decimal(x) / (Decimal(a) * Decimal(a))) - Decimal(b)
        c = math.atan(Decimal(a) / (Decimal(b) - Decimal(d)))
        d_deg = math.degrees(Decimal(c))
        print(Decimal(90) - Decimal(d_deg))


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
from decimal import *
import math

def main():
    a, b, x = map(int, input().split())
    if Decimal(a) * Decimal(b) / Decimal(2) >= Decimal(x) / Decimal(a):
        tmp = Decimal(2) * Decimal(x) / (Decimal(a) * Decimal(b))
        c = math.atan(Decimal(tmp) / Decimal(b))
        d_deg = math.degrees(Decimal(c))
        print(Decimal(90) - Decimal(d_deg))
    else:
        d = (Decimal(2) * Decimal(x) / (Decimal(a) * Decimal(a))) - Decimal(b)
        c = math.atan(Decimal(a) / (Decimal(b) - Decimal(d)))
        d_deg = math.degrees(Decimal(c))
        print(Decimal(90) - Decimal(d_deg))


if __name__ == "__main__":
    main()

Fixed submission:
from decimal import *
import math

def main():
    a, b, x = map(int, input().split())
    if a * a * b == x:
        print(0)
        exit()
    if Decimal(a) * Decimal(b) / Decimal(2) >= Decimal(x) / Decimal(a):
        tmp = Decimal(2) * Decimal(x) / (Decimal(a) * Decimal(b))
        c = math.atan(Decimal(tmp) / Decimal(b))
        d_deg = math.degrees(Decimal(c))
        print(Decimal(90) - Decimal(d_deg))
    else:
        d = (Decimal(2) * Decimal(x) / (Decimal(a) * Decimal(a))) - Decimal(b)
        c = math.atan(Decimal(a) / (Decimal(b) - Decimal(d)))
        d_deg = math.degrees(Decimal(c))
        print(Decimal(90) - Decimal(d_deg))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
sort_A = sorted(A)
sort_F = sorted(F,reverse=True)

def check(x):
    cnt = 0
    for i in range(N):
        tmp = x // sort_F[i]
        cnt += max(0, sort_A[i] - tmp)
    return cnt <= K



def main():
    ok = 10 ** 22
    ng = -1

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid

    print(ok) 

if __name__ == "__main__":
    main()

Fixed submission:
def isOK(mid,N,K,sort_F,sort_A):
    cnt = 0
    for i in range(N):
        cnt += max(sort_A[i] - (mid // sort_F[i]),0)
    return cnt <= K

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    sort_A = sorted(A)
    sort_F = sorted(F, reverse=True)

    ng = -1
    ok = 10 ** 12 + 5
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if isOK(mid,N,K,sort_F,sort_A):
            ok = mid
        else:
            ng = mid

    print(ok)



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            if i == j:
                continue
            for k in range(max(i,j)+1,N):
                if sort_L[i] + sort_L[j] > sort_L[k]:
                    cnt += 1
                else:
                    break

    print(cnt)

    

if __name__ == "__main__":
    main()

Fixed submission:
import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            tmp = bisect.bisect_left(sort_L,sort_L[i] + sort_L[j])
            if tmp - 1 > j:
                cnt += tmp - j - 1
    print(cnt)

    

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            if i == j:
                continue
            for k in range(N-1,max(i,j),-1):
                if sort_L[i] + sort_L[j] > sort_L[k]:
                    cnt += 1

    print(cnt)

    

if __name__ == "__main__":
    main()

Fixed submission:
import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    sort_L = sorted(L)
    cnt = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            tmp = bisect.bisect_left(sort_L,sort_L[i] + sort_L[j])
            if tmp - 1 > j:
                cnt += tmp - j - 1
    print(cnt)

    

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

def cf(x1,x2):
    cf=[]
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def main():
    A, B = map(int, input().split())

    C = cf(A,B)

    cnt = 1
    for c in C:
        if is_prime(c):
            cnt += 1

    print(cnt)

main()

Fixed submission:
import itertools

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

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def main():
    A, B = map(int, input().split())

    div_A = divisor(A)
    div_B = divisor(B)
    C = list(set(div_A) & set(div_B))
    cnt = 1
    for c in C:
        if is_prime(c):
            cnt += 1

    print(cnt)

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

    sort_A = sorted(A, reverse=True)


    for _ in range(M):
        sort_A[sort_A.index(max(sort_A))] = max(sort_A) // 2

    print(sum(sort_A))

main()

Fixed submission:
import heapq
def func(n):
    return -n

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

    heapq.heapify(A)

    for _ in range(M):
        tmp = -heapq.heappop(A) // 2
        heapq.heappush(A,-tmp)

    print(-sum(A))

main()

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

    sort_A = sorted(A, reverse=True)

    for _ in range(M):
        sort_A[0] = sort_A[0] // 2
        sort_A.sort(reverse=True)

    print(sum(sort_A))

main()

Fixed submission:
import heapq
def func(n):
    return -n

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

    heapq.heapify(A)

    for _ in range(M):
        tmp = -heapq.heappop(A) // 2
        heapq.heappush(A,-tmp)

    print(-sum(A))

main()