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

def read():
    A, B = map(int, input().strip().split())
    return A, B

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)
    return divisors

def solve(A, B):
    gcd = math.gcd(A, B)
    divisors = sorted(make_divisors(gcd))
    table = [True] * len(divisors)
    for i in range(1, len(divisors)):
        for j in range(i+1, len(divisors)):
            if table[j] and divisors[j] % divisors[i] == 0:
                table[j] = False
    divisors = [divisors[i] for i in range(len(divisors)) if table[i]]
    return len(divisors)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


Fixed submission:
import fractions

def read():
    A, B = map(int, input().strip().split())
    return A, B

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)
    return divisors

def solve(A, B):
    gcd = fractions.gcd(A, B)
    divisors = sorted(make_divisors(gcd))
    table = [True] * len(divisors)
    for i in range(1, len(divisors)):
        for j in range(i+1, len(divisors)):
            if table[j] and divisors[j] % divisors[i] == 0:
                table[j] = False
    divisors = [divisors[i] for i in range(len(divisors)) if table[i]]
    return len(divisors)

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = set()
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans.add(i)
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = []
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans += [i]
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = []
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans += [i]
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = []
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans += [i]
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
Buggy python submission (verdict: Runtime Error):
# start -> ダム -> 山 -> end で2部グラフを作って最大流を求めれば求まるはず


MAX_V = 100002
used = [False] * MAX_V
edge = [[] for _ in range(MAX_V)]

class Edge():

    def __init__(self, to, cap, rev):
        self.to = to
        self.cap = cap
        self.rev = rev

def init_used():
    for i in range(MAX_V):
        used[i] = False

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A

def build_graph(N, A, INF=10000000000):
    START = 2 * N
    END = 2 * N + 1
    for i in range(N):
        edge[START].append(Edge(i, A[i], len(edge[i])))
        edge[i].append(Edge(START, 0, len(edge[START])))
    for i in range(N):
        j = N + ((i - 1) % N)
        edge[i].append(Edge(N+i, INF, len(edge[N+i])))
        edge[j].append(Edge(N + j, INF, len(edge[N + j])))
        edge[N+i].append(Edge(N + i, 0, len(edge[i])))
        edge[N+j].append(Edge(N + j, 0, len(edge[j])))
    for i in range(N):
        edge[N+i].append(Edge(END, INF, len(edge[END])))
        edge[END].append(Edge(N+i, 0, len(edge[N+i])))
    return edge, START, END


def dfs(edge, weight, v, t, f=10000000000):
    if v == t:
        return f
    used[v] = True
    for i in range(len(edge[v])):
        to = edge[v][i]
        if not used[to] and weight[v][i] > 0:
            d = dfs(to, t, min(f, weight[v][i]))
            if d > 0:
                weight[v][i] -= d
                edge[v]


def maximum_flow(edge, s, t):
    V = len(edge)
    while True:
        init_used()
        d = dfs(edge, s, t)
        return 0
    

def solve(N, A):
    # 0~N-1: damu, N~2N-1: yama, 2N: s, 2N+1: t
    edge, START, END = build_graph(N, A)
    maximum_flow(edge, START, END)
    return 0


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


Fixed submission:
def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A

def solve(N, A):
    x = [0 for i in range(N)]
    x[0] = sum([A[i]*(-1)**i for i in range(0, N)]) // 2
    for i in range(0, N-1):
        x[i+1] = A[i] - x[i]
    x = [2 * x[i] for i in range(N)]
    return ' '.join(map(str, x))

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
Buggy python submission (verdict: Runtime Error):
from operator import mul
from functools import reduce

def nCr(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 read():
    N, K = list(map(int, input().strip().split()))
    return N, K

def solve(N, K):
    if N == K:
        print(1)
        for i in range(2, K + 1):
            print(0)
    else:
        for i in range(1, K + 1):
            count = nCr(N - K + 1, i) * nCr(K - 1, i - 1)
            print(count % (10**9 + 7))

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)


Fixed submission:
from operator import mul
from functools import reduce

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

def read():
    N, K = list(map(int, input().strip().split()))
    return N, K

def solve(N, K):
    for i in range(1, K + 1):
        count = nCr(N - K + 1, i) * nCr(K - 1, i - 1)
        print(count % (10**9 + 7))

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)

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

def nCr(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 read():
    N, K = list(map(int, input().strip().split()))
    return N, K

def solve(N, K):
    for i in range(1, K + 1):
        count = nCr(N - K + 1, i) * nCr(K - 1, i - 1)
        print(count % (10**9 + 7))

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)


Fixed submission:
from operator import mul
from functools import reduce

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

def read():
    N, K = list(map(int, input().strip().split()))
    return N, K

def solve(N, K):
    for i in range(1, K + 1):
        count = nCr(N - K + 1, i) * nCr(K - 1, i - 1)
        print(count % (10**9 + 7))

if __name__ == '__main__':
    inputs = read()
    solve(*inputs)
Buggy python submission (verdict: Runtime Error):
from operator import itemgetter

def read():
    N, M = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    B = []
    C = []
    for m in range(M):
        b, c = list(map(int, input().strip().split()))
        B.append(b)
        C.append(c)
    return N, M, A, B, C


def solve(N, M, A, B, C):
    cindex_desc = sorted(range(M), key=lambda k: C[k])
    A = sorted(A)
    left_index = 0
    for i in reversed(cindex_desc):
        for j in range(B[i]):
            if A[left_index] < C[i]:
                A[left_index] = C[i]
                left_index += 1
            else:
                break
    return sum(A)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


Fixed submission:
def read():
    N, M = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    B = []
    C = []
    for m in range(M):
        b, c = list(map(int, input().strip().split()))
        B.append(b)
        C.append(c)
    return N, M, A, B, C


def solve(N, M, A, B, C):
    cindex_desc = sorted(range(M), key=lambda k: C[k])
    A = sorted(A)
    left_index = 0
    for i in reversed(cindex_desc):
        for j in range(B[i]):
            if left_index >= N:
                break
            if A[left_index] < C[i]:
                A[left_index] = C[i]
                left_index += 1
            else:
                break
    return sum(A)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from functools import reduce
from operator import xor


def read():
    M, K = map(int, input().strip().split())
    return M, K


def solve(M, K):
    seq = [str(0) for i in range(2**(M+1))]
    if K == 0:
        for i in range(2**M):
            seq[2*i] = str(i)
            seq[2*i+1] = str(i)
    else:
        # K ... 0 K rev(...) 0, xor(...) == K の形を作れればOK
        S = [a for a in range(2**M) if a not in (0, K)]
        if M == 1 or reduce(xor, S) != K:
            return -1
        j = 0
        for i in range(2**M-2):
            j += 1
            if j == K:
                j += 1
            seq[i+1] = str(j)
            seq[2**(M+1) - i - 2] = str(j)
        seq[0] = str(K)
        seq[2**M] = str(K)
    return " ".join(seq)
    


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


Fixed submission:
import sys
input = sys.stdin.readline
from functools import reduce
from operator import xor


def read():
    M, K = map(int, input().strip().split())
    return M, K


def solve(M, K):
    seq = [str(0) for i in range(2**(M+1))]
    if K == 0:
        for i in range(2**M):
            seq[2*i] = str(i)
            seq[2*i+1] = str(i)
    else:
        if K >= 2**M:
            return -1
        # (A) K ... 0 K 0 rev(...), xor(...) == K の形を作れればOK
        S = [a for a in range(2**M) if a not in (0, K)]
        if len(S) == 0 or reduce(xor, S) != K:
            return -1
            
        j = 0
        for i in range(2**M-2):
            j += 1
            if j == K:
                j += 1
            seq[i+1] = str(j)
            seq[2**(M+1) - i - 1] = str(j)
        seq[0] = str(K)
        seq[2**M] = str(K)
        
    return " ".join(seq)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))
Buggy python submission (verdict: Runtime Error):
def read():
    N, K = list(map(int, input().strip().split()))
    A = list(map(int, input().strip().split()))
    return N, K, A


def binary_digits(x):
    digit = 0
    while x > 0:
        x >>= 1
        digit += 1
    return digit


def maximum_X(N, K, A):
    digitK = binary_digits(K)
    counts = []
    bitmask = 1
    for d in range(digitK):
        count = 0
        for i in range(N):
            if A[i] & bitmask == bitmask:
                count += 1
        counts.append(count)
        bitmask <<= 1

    X = 0
    bitmask = 1
    for d in range(digitK):
        if counts[d] * 2 <= N:
            if K & bitmask == bitmask:
                X += bitmask
        bitmask <<= 1
    return X


def f(x, A):
    y = 0
    for a in A:
        y += (x ^ a)
    return y


def solve(N, K, A):
    X = maximum_X(N, K, A)
    return f(X, A)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


Fixed submission:
def read():
    T, X = map(int, input().strip().split())
    return T, X


def solve(T, X):
    return T / X


if __name__ == '__main__':
    inputs = read()
    print("%f" % solve(*inputs))
Buggy python submission (verdict: Runtime Error):
def read():
    N = int(input().strip())
    L = map(int, input().strip().split())
    return N, L


def solve(N, L):
    L = sorted(L)
    return "Yes" if L[-1] < sum(L[:-1]) else "No"


if __name__ == '__main__':
    inputs = read()
    print("%f" % solve(*inputs))


Fixed submission:
def read():
    N = int(input().strip())
    L = map(int, input().strip().split())
    return N, L


def solve(N, L):
    L = sorted(L)
    return "Yes" if L[-1] < sum(L[:-1]) else "No"


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
Buggy python submission (verdict: Runtime Error):
def read():
    N, K = map(int, input().strip().split())
    A = map(int, input().strip().split())
    return N, K, A


def binary_digits(x):
    digit = 0
    while x > 0:
        x >>= 1
        digit += 1
    return digit


def maximum_X(N, K, A):
    digitK = binary_digits(K)
    counts = []
    bitmask = 1
    for d in range(digitK):
        count = 0
        for i in range(N):
            if A[i] & bitmask == bitmask:
                count += 1
        counts.append(count)
        bitmask <<= 1

    X = 0
    bitmask = 1
    for d in range(digitK):
        if counts[d] * 2 < N:
            X += bitmask
        bitmask <<= 1
    return X


def f(x, A):
    y = 0
    for a in A:
        y += (x ^ a)
    return y


def solve(N, K, A):
    X = maximum_X(N, K, A)
    return f(X, A)


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


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


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    L = max(K, max(A), 1).bit_length()
    k = [0 for i in range(L)]
    i = 0
    while K:
        k[i] += K & 1
        i += 1
        K >>= 1
    b = [0 for i in range(L)]
    for a in A:
        i = 0
        x = a
        while x:
            b[i] += x & 1
            i += 1
            x >>= 1
    k = k[::-1]
    b = b[::-1]
    # dp[i][1]: 上位iビットがKと等しいときの最大値
    # dp[i][0]: 上位iビットがKより小さいときの最大値
    dp = [[-1, -1] for i in range(L+1)]
    dp[0][1] = 0
    for i in range(L):
        if dp[i][0] >= 0:
            dp[i+1][0] = (dp[i][0] << 1) + max(b[i], N-b[i])
        if dp[i][1] >= 0:
            if k[i] == 1:
                dp[i+1][0] = max(dp[i+1][0], (dp[i][1] << 1) + b[i])
                dp[i+1][1] = (dp[i][1] << 1) + (N-b[i])
            else:
                dp[i+1][1] = (dp[i][1] << 1) + (b[i])
    return max(dp[L][1], dp[L][0])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
Buggy python submission (verdict: Runtime Error):
import numpy as np


def read():
    N = int(input().strip())
    H = list(map(int, input().strip().split()))
    return N, H

def solve(N, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i in range(1, N):
        left, right = INF, INF
        if i >= 1:
            left = dp[i-1] + abs(H[i-1] - H[i])
        if i >= 2:
            right = dp[i-2] + abs(H[i-2] - H[i])
        dp[i] = min(left, right)
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Fixed submission:
def read():
    N = int(input().strip())
    H = list(map(int, input().strip().split()))
    return N, H

def solve(N, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i in range(1, N):
        left, right = INF, INF
        if i >= 1:
            left = dp[i-1] + abs(H[i-1] - H[i])
        if i >= 2:
            right = dp[i-2] + abs(H[i-2] - H[i])
        dp[i] = min(left, right)
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product


def read():
    N, K = list(map(int, input().strip().split()))
    H = list(map(int, input().strip().split()))
    return N, K, H

def solve(N, K, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i, k in product(range(1, N), range(1, K+1)):
        if 0 <= i - k:
            dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Fixed submission:
from itertools import product


def read():
    N, K = list(map(int, input().strip().split()))
    H = list(map(int, input().strip().split()))
    return N, K, H

def solve(N, K, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i, k in product(range(1, N), range(1, K+1)):
        if 0 <= i - k:
            dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Buggy python submission (verdict: Time Limit Exceeded):
def read():
    N, K = list(map(int, input().strip().split()))
    H = list(map(int, input().strip().split()))
    return N, K, H

def solve(N, K, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i in range(1, N):
        v = INF
        for k in range(1, K+1):
            if 0 <= i - k < N:
                v = min(v, dp[i-k] + abs(H[i] - H[i-k]))
        dp[i] = v
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Fixed submission:
from itertools import product


def read():
    N, K = list(map(int, input().strip().split()))
    H = list(map(int, input().strip().split()))
    return N, K, H

def solve(N, K, H, INF=10**9):
    dp = [INF for i in range(N)]
    dp[0] = 0
    for i, k in product(range(1, N), range(1, K+1)):
        if 0 <= i - k:
            dp[i] = min(dp[i], dp[i-k] + abs(H[i] - H[i-k]))
    return dp[N-1]

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i, j in product(range(N), range(W+1)):
        u = dp[i][j]
        if j - pairs[i][0] >= 0:
            u = max(u, dp[i][j-pairs[i][0]]+pairs[i][1])
        dp[i+1][j] = u
    return max(dp[N])

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Fixed submission:
from itertools import product


def read():
    N, W = list(map(int, input().split()))
    pairs = list()
    for i in range(N):
        w, v = list(map(int, input().split()))
        pairs.append((w, v))
    return N, W, pairs

def solve(N, W, pairs):
    dp = [[0 for j in range(W+1)] for i in range(N+1)]
    for i, j in product(range(N), range(W+1)):
        u = dp[i][j]
        if j - pairs[i][0] >= 0:
            u = max(u, dp[i][j-pairs[i][0]]+pairs[i][1])
        dp[i+1][j] = u
    return max(dp[N])

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N, M = map(int, input().strip().split())
    E_out = [list() for i in range(N)]
    E_in = [list() for i in range(N)]
    for i in range(M):
        x, y = map(int, input().strip().split())
        E_out[x-1].append(y-1)  # x -> E_out[x]
        E_in[y-1].append(x-1)   # E_in[x] -> x
    return N, M, E_in, E_out


def solve(N, M, E_in, E_out):
    dp = [-1 for i in range(N)]
    q = deque()
    for x in range(N):
        if len(E_out[x]) == 0:
            q.append(x)
            dp[x] = 0
    while q:
        x = q.pop()
        for y in E_in[x]:
            q.append(y)
            dp[y] = max(dp[y], dp[x] + 1)
    return max(dp)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


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


def read():
    N, M = map(int, input().strip().split())
    parents = [list() for i in range(N)]
    n_children = [0 for i in range(N)]
    for i in range(M):
        x, y = map(int, input().strip().split())
        n_children[x-1] += 1  # x -> E_out[x]
        parents[y-1].append(x-1)   # E_in[x] -> x
    return N, M, n_children, parents


def solve(N, M, n_children, parents):
    dp = [0 for i in range(N)]
    q = deque()
    r = deque()
    for x in range(N):
        if n_children[x] == 0:
            q.append(x)
    while q:
        x = q.pop()
        r.append(x)
        for parent in parents[x]:
            n_children[parent] -= 1
            if n_children[parent] == 0:
                q.append(parent)
    
    while r:
        x = r.pop()
        for y in parents[x]:
            dp[x] = max(dp[x], dp[y]+1)
    return max(dp)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))