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


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def cut(A, k, size) -> bool:
    cnt = 0
    for a in A:
        cnt += a // size
        if a % size == 0:
            cnt -= 1
        if cnt > k:
            return False
    if cnt <= k:
        return True


def main():
    n, k = input_int_list()
    A = input_int_list()

    left = 0
    right = max(A)

    fail = 0
    success = right

    while True:
        mid = (left + right) // 2
        res = cut(A, k, mid)
        if res:
            right = mid - 1
            success = min(mid, success)
        else:
            left = mid + 1
            fail = max(mid, fail)
        if left == right:
            break
    print(success)
    return


if __name__ == "__main__":
    main()


Fixed submission:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def cut(A, k, size) -> bool:
    cnt = 0
    for a in A:
        cnt += a // size
        if a % size == 0:
            cnt -= 1
        if cnt > k:
            return False
    if cnt <= k:
        return True


def main():
    n, k = input_int_list()
    A = input_int_list()

    left = 0
    right = max(A)

    while right > left + 1:
        mid = (left + right) // 2
        res = cut(A, k, mid)
        if res:
            right = mid
        else:
            left = mid
    print(right)
    return


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    n,k = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()] 
    cur_mul = [1] * n
    for i in range(n):
        if i == 0:
            cur_mul[i] = A[i]
        elif i > 0 and i <= k-1:
            cur_mul[i] = A[i] * cur_mul[i - 1]
        elif i > k-1:
            cur_mul[i] = cur_mul[i - 1] * A[i] // A[i - k]
            if cur_mul[i] > cur_mul[i - 1]:
                print("Yes")
            else:
                print("No")
    return

if __name__ == "__main__":
    main()


Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    n,k = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()] 

    for i in range(k, n):
        if A[i] > A[i - k]:
            print("Yes")
        
        else:
            print("No")
    return

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    ans = 0
    for i in range(1,N+1):
        for j in range(i,N+1,i):
            ans += j
    return ans

if __name__ == "__main__":
    print(main())




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

def main():
    N = int(input().strip())
    ans = 0
    for i in range(1,N+1):
        for j in range(i,N+1,i):
            ans += j
    return ans

if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    A_list = [int(i) for i in input().strip().split()]
    Q = int(input().strip())
    _sum = sum(A_list)
    num_count = Counter(A_list)
    for _ in range(Q):
        B, C = [int(i) for i in input().strip().split()]
        if B in num_count:
            if C in num_count:
                num_count[C] = num_count[C] + num_count[B]
            else:
                num_count[C] = num_count[B]
            del num_count[B]
            _sum = 0
            for k, v in num_count.items():
                _sum += k * v
            print(_sum)
        else:
            print(_sum)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import Counter
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    A_list = [int(i) for i in input().strip().split()]
    Q = int(input().strip())
    _sum = sum(A_list)
    num_count = Counter(A_list)
    for _ in range(Q):
        B, C = [int(i) for i in input().strip().split()]
        if B in num_count:
            if C in num_count:
                num_count[C] = num_count[C] + num_count[B]
            else:
                num_count[C] = num_count[B]

            _sum = _sum - (num_count[B] * B) + num_count[B] * C
            del num_count[B]
            print(_sum)
        else:
            print(_sum)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+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


def main():
    N = int(input().strip())
    if N == 1:
        return 0
    factors = factorization(N)
    ans = 0
    for factor in factors:
        counter = 1
        while True:
            if factor[1] >= counter:
                selected.add(factor[0]**counter)
                factor[1] -= counter
                counter += 1
                ans += 1
            else:
                break
    return ans


if __name__ == "__main__":
    print(main())


Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+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


def main():
    N = int(input().strip())
    if N == 1:
        return 0
    factors = factorization(N)
    ans = 0
    for factor in factors:
        counter = 1
        while True:
            if factor[1] >= counter:
                factor[1] -= counter
                counter += 1
                ans += 1
            else:
                break
    return ans


if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    S = int(input().strip())
    return S.replace("?","D")

if __name__ == "__main__":
    print(main())

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    S = input().strip()
    return S.replace("?","D")

if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    A, B, N = [int(i) for i in input().strip().split()]
    ans = 0
    if N >= B:
        for n in range(B-1, N+1, B):
            ans = max(ans, ((A * n) // B) - (A * (n // B)))
    else:
        ans = ((A * N) // B) - (A * (N // B))
    return ans


if __name__ == "__main__":
    print(main())


Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    A, B, N = [int(i) for i in input().strip().split()]
    ans = 0
    if N >= B:
        if A >= B:
            n = range(B - 1, N + 1, B)[-1]
        else:
            n = range(B - 1, N + 1, B)[0]
        ans = ((A * n) // B) - (A * (n // B))
    else:
        ans = ((A * N) // B) - (A * (N // B))
    return ans


if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
import sys
from functools import lru_cache
from functools import reduce
from operator import mul
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


@lru_cache(None)
def cmb(n: int, r: int):
    if n < r:
        return 0
    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 main():
    _ = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    cnts = Counter(A)
    for a in A:
        tmp = 0
        cnts[a] -= 1
        for k, v in cnts.items():
            tmp += cmb(v, 2)
        print(tmp)
        cnts[a] += 1
    return


if __name__ == "__main__":
    main()

Fixed submission:
from collections import Counter
import sys
from functools import lru_cache
from functools import reduce
from operator import mul
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


@lru_cache(None)
def cmb(n: int, r: int):
    if n < r:
        return 0
    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 main():
    _ = int(input().strip())
    A = [int(i) for i in input().strip().split()]
    cnts = Counter(A)
    d = {}
    _sum = 0
    for k, v in cnts.items():
        d[k] = (cmb(v, 2), cmb(v - 1, 2))
        _sum += d[k][0]
    for a in A:
        dif = d[a][0] - d[a][1]
        print(_sum - dif)
    return


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = input()
    q = input_int()
    inverse = False
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            inverse = not inverse
        else:
            if (data[1] == "1" and not inverse) or (data[1] == "2" and inverse):
                s = data[2] + s
            else:
                s = s + data[2]
    if inverse:
        print(s[::-1])
    else:
        print(s)
    return


if __name__ == "__main__":
    main()


Fixed submission:
import sys
# sys.setrecursionlimit(100000)
from collections import deque


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = deque(list(input()))
    q = input_int()
    inverse = False
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            inverse = not inverse
        else:
            if (data[1] == "1" and not inverse) or (data[1] == "2" and inverse):
                s.appendleft(data[2])
            else:
                s.append(data[2])
    if inverse:
        print("".join(reversed(s)))
    else:
        print("".join(s))
    return


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = input()
    q = input_int()
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            s = s[::-1]
        else:
            if data[1] == "1":
                s = data[2] + s
            else:
                s = s + data[2]
    print(s)
    return


if __name__ == "__main__":
    main()


Fixed submission:
import sys
# sys.setrecursionlimit(100000)
from collections import deque


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    s = deque(list(input()))
    q = input_int()
    inverse = False
    for _ in range(q):
        data = input().split()
        if len(data) == 1:
            inverse = not inverse
        else:
            if (data[1] == "1" and not inverse) or (data[1] == "2" and inverse):
                s.appendleft(data[2])
            else:
                s.append(data[2])
    if inverse:
        print("".join(reversed(s)))
    else:
        print("".join(s))
    return


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    ans = [0 for _ in range(N)]
    if N > 1:
        ans[0] = 1
    for i, s in enumerate(S):
        if s[0] == 1 and s[1] == 0:
            if N > 1:
                print(-1)
                return
        for i2, s2 in enumerate(S):
            if i == i2:
                continue
            if s[0] == s2[0]:
                if s[1] != s2[1]:
                    print(-1)
                    return
        ANS[s[0] - 1] = s[1]
    ans = int(''.join([str(n) for n in ANS]))
    print(ans)
    return
 
 
if __name__ == '__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    ans = [0 for _ in range(N)]
    if N > 1:
        ans[0] = 1
    for i, s in enumerate(S):
        if s[0] == 1 and s[1] == 0:
            if N > 1:
                print(-1)
                return
        for i2, s2 in enumerate(S):
            if i == i2:
                continue
            if s[0] == s2[0]:
                if s[1] != s2[1]:
                    print(-1)
                    return
        ans[s[0] - 1] = s[1]
    ans = int(''.join([str(n) for n in ans]))
    print(ans)
    return


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc156/tasks/abc156_d

import sys
input = sys.stdin.readline


from operator import mul
from functools import reduce

def pow_k(x, n):
    """
    O(log n)
    """
    MOD = 10**9 + 7
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    MOD = 10**9 + 7
    over,under  = 1,1
    for i in range(n, n - r, -1):
        over = over*i
    # over = reduce(mul, range(n, n - r, -1))
    for i in range(1, r + 1):
        under = under*i
    return over // under

def main():
    MOD = 10**9 + 7
    n,a,b = [int(i) for i in input().strip().split()]
    _sum = ((pow_k(2, n))-1) % MOD
    cmb_a = cmb(n, a) %MOD
    cmb_b = cmb(n, b) % MOD
    ans = (_sum - cmb_a - cmb_b) % MOD
    
    print(ans)
    

if __name__ == "__main__":
    main()

Fixed submission:
# https://atcoder.jp/contests/abc156/tasks/abc156_d

import sys
input = sys.stdin.readline


from operator import mul
from functools import reduce

def pow_k(x, n, mod):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return (K * x) %mod


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def main():
    n, a, b = [int(i) for i in input().strip().split()]
    MOD = 10**9 + 7
    _sum = ((pow_k(2, n,MOD))-1) % MOD
    cmb_a = combination(n, a,MOD)
    cmb_b = combination(n, b,MOD)
    ans = (_sum - cmb_a - cmb_b) % MOD
    
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
from copy import deepcopy
input = sys.stdin.readline


def bfs(table, i, j):
    dq = deque()
    if table[i][j] == "#":
        return -1
    h = len(table)
    w = len(table[0])
    ans = 0
    dq.append((i, j, 0))  # x,y,distance
    while dq:
        x, y, dis = dq.popleft()
        ans = max(ans, dis)
        if x > 0 and (x - 1, y) and table[x - 1][y] != "#":
            dq.append((x - 1, y, dis + 1))
            table[x - 1][y] = "#"
        if x < h - 1 and (x + 1, y) and table[x + 1][y] != "#":
            dq.append((x + 1, y, dis + 1))
            table[x + 1][y] = "#"
        if y > 0 and (x, y - 1) and table[x][y - 1] != "#":
            dq.append((x, y - 1, dis + 1))
            table[x][y - 1] = "#"
        if y < w - 1 and (x, y + 1) and table[x][y + 1] != "#":
            dq.append((x, y + 1, dis + 1))
            table[x][y + 1] = "#"
    return ans


def main():
    h, w = [int(i) for i in input().strip().split()]
    grid = [list(input().strip()) for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                _grid = deepcopy(grid)
                max_path = bfs(_grid, i, j)
                ans = max(ans, max_path)

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
c = input()
print(chr(ord(c)+1))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def main():
    n,a,b = [int(i) for i in input().strip().split()]
    if abs(a - b) % 2 == 0:
        print(abs(a - b) // 2)
    else:
        ans = min(a - 1, n - b) - 1 + (A - B - 1) // 2
        print(ans)
    return 



if __name__ == "__main__":
    main()

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


def main():
    n,a,b = [int(i) for i in input().strip().split()]
    if (b-a) % 2 == 0:
        print(abs(b - a) // 2)
    else:
        ans = min(a - 1, n - b) + 1 + (b - a - 1) // 2
        print(ans)
    return 



if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    a_l = [int(i) for i in input().split()]
    if 1 not in a_l:
        print(-1)
        sys.exit()
    counter = 1
    b = 0
    for i in a_l:
        if i == counter:
            counter += 1
        else:
            b += 1
    print(b)
    sys.exit()


if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input())
    a_l = [int(i) for i in input().split()]
    if 1 not in a_l:
        print(-1)
        sys.exit()
    counter = 1
    b = 0
    for i in a_l:
        if i == counter:
            counter += 1
        else:
            b += 1
    print(b)
    sys.exit()


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    h, w, k = input_int_list()
    num = 0
    grid = []
    for _ in range(h):
        grid.append(list(input()))

    # 分割統治法
    def solver(x_b, y_b, x_e, y_e):  # x_end,y_endは包含/排他範囲
        # いちごの数を数える
        cnt = 0
        first = None
        second = None
        for i in range(x_b, x_e):
            for j in range(y_b, y_e):
                if grid[i][j] == "#":
                    cnt += 1
                    if not first:
                        first = [i, j]
                    elif not second:
                        second = [i, j]
        if cnt == 1:
            nonlocal num
            num += 1
            for i in range(x_b, x_e):
                for j in range(y_b, y_e):
                    grid[i][j] = num
            return
        # いちごが少なくとも1つ含まれるように分割する
        if cnt > 1:
            if first[0] != second[0]:
                x_edge = max(first[0], second[0])
                solver(x_b, y_b, x_edge, y_e)
                solver(x_edge, y_b, x_e, y_e)
            elif first[1] != second[1]:
                y_edge = max(first[1], second[1])
                solver(x_b, y_b, x_e, y_edge)
                solver(x_b, y_edge, x_e, y_e)

    solver(0, 0, h, w)
    for line in grid:
        print(*line)

    return


if __name__ == "__main__":
    main()


Fixed submission:
import sys
sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    h, w, k = input_int_list()
    num = 0
    grid = []
    for _ in range(h):
        grid.append(list(input()))

    # 分割統治法
    def solver(x_b, y_b, x_e, y_e):  # x_end,y_endは包含/排他範囲
        # いちごの数を数える
        cnt = 0
        first = None
        second = None
        for i in range(x_b, x_e):
            for j in range(y_b, y_e):
                if grid[i][j] == "#":
                    cnt += 1
                    if not first:
                        first = [i, j]
                    elif not second:
                        second = [i, j]
        if cnt == 1:
            nonlocal num
            num += 1
            for i in range(x_b, x_e):
                for j in range(y_b, y_e):
                    grid[i][j] = num
            return
        # いちごが少なくとも1つ含まれるように分割する
        if cnt > 1:
            if first[0] != second[0]:
                x_edge = max(first[0], second[0])
                solver(x_b, y_b, x_edge, y_e)
                solver(x_edge, y_b, x_e, y_e)
            elif first[1] != second[1]:
                y_edge = max(first[1], second[1])
                solver(x_b, y_b, x_e, y_edge)
                solver(x_b, y_edge, x_e, y_e)

    solver(0, 0, h, w)
    for line in grid:
        print(*line)

    return


if __name__ == "__main__":
    main()