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

class UnionFind:

    def __init__(self, N):
        self.raw = [i for i in range(N)]

    def root(self, i):
        if self.raw[i] == i:
            return i
        self.raw[i] = self.root(self.raw[i])
        return self.raw[i]

    def unite(self, a, b):
        a_root = self.root(a)
        b_root = self.root(b)
        self.raw[a_root] = b_root

    def is_same(self, a, b):
        return self.root(a) == self.root(b)


def solve(N, M, K, AB, CD):
    uf = UnionFind(N)
    minus_count = [0 for _ in range(N)]
    for a, b in AB:
        uf.unite(a - 1, b - 1)
        minus_count[a - 1] += 1
        minus_count[b - 1] += 1
    for c, d in CD:
        if uf.is_same(c - 1, d - 1):
            minus_count[c - 1] += 1
            minus_count[d - 1] += 1
    counter = collections.Counter()
    roots = [uf.root(i) for i in range(N)]
    counter.update(roots)

    ans = []
    for i in range(N):
        ans.append(str(counter[uf.root(i)] - minus_count[i] - 1))
    return " ".join(ans)

if __name__ == "__main__":
    N, M, K = tuple(map(int, input().split(" ")))
    AB = []
    for _ in range(M):
        AB.append(tuple(map(int, input().split(" "))))
    CD = []
    for _ in range(K):
        CD.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, K, AB, CD))


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

class UnionFind:

    def __init__(self, N):
        self.raw = [i for i in range(N)]

    def root(self, i):
        if self.raw[i] == i:
            return i
        self.raw[i] = self.root(self.raw[i])
        return self.raw[i]

    def unite(self, a, b):
        a_root = self.root(a)
        b_root = self.root(b)
        self.raw[a_root] = b_root

    def is_same(self, a, b):
        return self.root(a) == self.root(b)


def solve(N, M, K, AB, CD):
    uf = UnionFind(N)
    minus_count = [0 for _ in range(N)]
    for a, b in AB:
        uf.unite(a - 1, b - 1)
        minus_count[a - 1] += 1
        minus_count[b - 1] += 1
    for c, d in CD:
        if uf.is_same(c - 1, d - 1):
            minus_count[c - 1] += 1
            minus_count[d - 1] += 1
    counter = collections.Counter()
    roots = [uf.root(i) for i in range(N)]
    counter.update(roots)

    ans = []
    for i in range(N):
        ans.append(str(counter[uf.root(i)] - minus_count[i] - 1))
    return " ".join(ans)

if __name__ == "__main__":
    N, M, K = tuple(map(int, input().split(" ")))
    AB = []
    for _ in range(M):
        AB.append(tuple(map(int, input().split(" "))))
    CD = []
    for _ in range(K):
        CD.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, K, AB, CD))
Buggy python submission (verdict: Time Limit Exceeded):

def partsolve(As, x):
    """
    :param As:
    :param x:
    :return: Asの積のペアの中で、x未満となるペアの個数
    """
    count = 0
    for i, a in enumerate(As):
        if a >= 0:
            l = 0
            r = len(As) - 1
            if As[r] * a < x:
                count += len(As)
            elif As[l] * a >= x:
                count += 0
            else:
                while r - l > 1:
                    m = l + (r - l) // 2
                    if As[m] * a < x:
                        l = m
                    else:
                        r = m
                count += l + 1
            if a * a < x:
                count -= 1
        else:
            # a < 0
            l = 0
            r = len(As) - 1
            if As[l] * a < x:
                count += len(As)
            elif As[r] * a >= x:
                count += 0
            else:
                while r - l > 1:
                    m = l + (r - l) // 2
                    if As[m] * a < x:
                        r = m
                    else:
                        l = m
                count += len(As) - r
            if a * a < x:
                count -= 1
    return count // 2

def solve(N, K, As):
    As = sorted(As)
    left = -10**18 - 1
    right = 10**18 + 1
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(As, mid)
        if c < K:
            left = mid
        else:
            right = mid
    return left

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))


Fixed submission:
import numpy as np


def partsolve(A, x, positive, zero, negative):
    """
    :param A:
    :param x:
    :return: Aの積のペアの中で、x以下となるペアの個数
    """
    count = 0
    if x >= 0:
        count = len(zero) * len(A)
    P = x // positive
    Pc = np.searchsorted(A, P, side='right')
    count += Pc.sum()

    N = (-x-1) // -negative
    Nc = np.searchsorted(A, N, side='right')
    Nc = len(A) - Nc
    count += Nc.sum()

    count -= np.count_nonzero(A * A <= x)
    return count // 2

def solve(N, K, As):
    A = np.array(sorted(As), np.int64)
    positive = A[A > 0]
    zero = A[A == 0]
    negative = A[A < 0]

    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = left + (right - left) // 2
        c = partsolve(A, mid, positive, zero, negative)
        if c < K:
            left = mid
        else:
            right = mid
    return right


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, K, As))
Buggy python submission (verdict: Time Limit Exceeded):
import math
H, N = tuple(map(int, input().split(" ")))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split(" "))))

minpower = 10 ** 8 + 1

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

for n in range(N):
    dp[n][0] = 0

for h in range(H + 1):
    for n in range(N):
        a, b = AB[n]

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print(dp[-1][H])

Fixed submission:
import math
H, N = tuple(map(int, input().split(" ")))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split(" "))))

minpower = 10 ** 8 + 1

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

for n in range(N):
    dp[n][0] = 0

for h in range(H + 1):
    for n in range(N):
        a, b = AB[n]

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print(dp[-1][H])

Buggy python submission (verdict: Time Limit Exceeded):
import math
H, N = tuple(map(int, input().split(" ")))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split(" "))))

minpower = 10 ** 10

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

for n in range(N):
    dp[n][0] = 0

for h in range(H + 1):
    for n in range(N):
        a, b = AB[n]

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print(dp[-1][H])

Fixed submission:
import math
H, N = tuple(map(int, input().split(" ")))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split(" "))))

minpower = 10 ** 8 + 1

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

for n in range(N):
    dp[n][0] = 0

for h in range(H + 1):
    for n in range(N):
        a, b = AB[n]

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print(dp[-1][H])
Buggy python submission (verdict: Runtime Error):
if __name__ == "__main__":
    S = Counter(input())
    if len(S) == 2 and all(v == 2 for v in S.values()):
        print("Yes")
    else:
        print("No")




Fixed submission:
from collections import Counter
if __name__ == "__main__":
    S = Counter(input())
    if len(S) == 2 and all(v == 2 for v in S.values()):
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
def solve(N):
    s = 1
    e = int(pow(N, 0.5)) + 1
    ds = []
    for i in range(s, e):
        if N % i == 0:
            m = N // i - 1
            if N // m == N % m:
                ds.append(N // i)

    return sum([i - 1 for i in ds])

if __name__ == "__main__":
    N = int(input())
    print(solve(N))


Fixed submission:
def solve(N):
    s = 1
    e = int(pow(N, 0.5)) + 1
    ds = []
    for i in range(s, e):
        if N % i == 0:
            m = (N // i) - 1
            if m and N // m == N % m:
                ds.append(N // i)
                # print(f"{N} = {m} * {N // m} + {N % m}")

    return sum([i - 1 for i in ds])


assert (solve(8) == 3 + 7)
assert (solve(10) == 4 + 9)
assert (solve(1000000000000) == 2499686339916)
if __name__ == "__main__":
    N = int(input())
    print(solve(N))
Buggy python submission (verdict: Runtime Error):
if __name__ == "__main__":
    b = tuple(map(int, input().split(" ")))
    if b == "A":
        print("T")
    if b == "T":
        print("A")
    if b == "C":
        print("G")
    if b == "G":
        print("C")

Fixed submission:
if __name__ == "__main__":
    b = input()
    if b == "A":
        print("T")
    if b == "T":
        print("A")
    if b == "C":
        print("G")
    if b == "G":
        print("C")
Buggy python submission (verdict: Time Limit Exceeded):
def psolve(k, Xs, N):
    arr = [[]]
    i = Xs[0]
    for x in Xs:
        if x <= i + k:
            arr[-1].append(x)
        else:
            arr.append([])
            arr[-1].append(x)
            i = x
            if len(arr) > N:
                break

    if len(arr) <= N:
        ans = sum([max(a) - min(a) for a in arr])
        return ans
    else:
        return 10 ** 9


def solve(N, M, Xs):
    Xs = sorted(Xs)
    ans = 10 ** 9
    for k in range(0, (Xs[-1] - Xs[0]) + 1):
        nans = psolve(k, Xs, N)
        ans = min(ans, nans)
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))


Fixed submission:

def solve(N, M, Xs):
    Xs = sorted(Xs)
    diffs = sorted([Xs[i+1] - Xs[i] for i in range(M-1)], reverse=True)
    return Xs[-1] - Xs[0] - sum(diffs[:N-1])


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))

Buggy python submission (verdict: Time Limit Exceeded):
def psolve(k, Xs, N):
    arr = [[]]
    i = Xs[0]
    for x in Xs:
        if x <= i + k:
            arr[-1].append(x)
        else:
            arr.append([])
            arr[-1].append(x)
            i = x
            if len(arr) > N:
                break

    if len(arr) <= N:
        ans = sum([max(a) - min(a) for a in arr])
        return ans
    else:
        return 10 ** 9


def solve(N, M, Xs):
    Xs = sorted(Xs)
    ans = 10 ** 9
    for k in range(0, (Xs[-1] - Xs[0]) + 1):
        ans = min(ans, psolve(k, Xs, N))
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))


Fixed submission:

def solve(N, M, Xs):
    Xs = sorted(Xs)
    diffs = sorted([Xs[i+1] - Xs[i] for i in range(M-1)], reverse=True)
    return Xs[-1] - Xs[0] - sum(diffs[:N-1])


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


def d(P):
    c = Counter()
    i = 2
    while (P > 1):
        if P % i == 0:
            c.update([i])
            P //= i
            i -= 1
        i += 1
    return c


def solve(N, P):
    c = d(P)
    ans = 1
    for k in [k for k, v in c.items() if v >= N]:
        ans *= k ** (c[k] // N)
    return ans


if __name__ == "__main__":
    N, X = tuple(map(int, input().split(" ")))
    print(solve(N, X))


Fixed submission:
from collections import Counter


def d(P):
    c = Counter()
    i = 2
    while (P > 1):
        if P % i == 0:
            c.update([i])
            P //= i
            i -= 1
        i += 1
        if i > P ** 0.5:
            c.update([P])
            break
    return c


def solve(N, P):
    c = d(P)
    ans = 1
    for k in [k for k, v in c.items() if v >= N]:
        ans *= k ** (c[k] // N)
    return ans

if __name__ == "__main__":
    N, X = tuple(map(int, input().split(" ")))
    print(solve(N, X))
Buggy python submission (verdict: Runtime Error):



def solve(N, K, As):
    alls = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            alls.append("{:061b}".format(sum(As[i:j])))
    print("alls", len(alls))
    def find(i, alls):
        if i > 60:
            return []
        ones = [a for a in alls if a[i] == "1"]
        if len(ones) < K:
            return find(i + 1, alls)
        elif len(ones) == K:
            return ones
        elif len(ones) > K:
            ret = find(i + 1, ones)
            if len(ret) == 0:
                return ones[0:K]
            else:
                return ret

    ans = find(0, alls)
    if len(ans):
        a = 0xFFFFFFFFFFF
        for p in ans:
            a &= int(p, 2)
        return a
    else:
        return 0

if __name__ == "__main__":
    l = input()
    N = int(l.split(" ")[0])
    K = int(l.split(" ")[1])
    As = [int(c) for c in input().split()]
    print(solve(N, K, As))


Fixed submission:
def solve(N, As):
    avg = sum(As) / N
    return min([(abs(c - avg), i) for i, c in enumerate(As)])[1]

if __name__ == "__main__":
    N = int(input())
    As = [int(c) for c in input().split()]
    print(solve(N, As))
Buggy python submission (verdict: Time Limit Exceeded):
def solve(N, K, As):
    alls = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            alls.append("{:061b}".format(sum(As[i:j])))
    def find(i, alls):
        if i > 60:
            return []
        ones = [a for a in alls if a[i] == "1"]
        if len(ones) < K:
            return find(i + 1, alls)
        elif len(ones) == K:
            return ones
        elif len(ones) > K:
            ret = find(i + 1, ones)
            if len(ret) == 0:
                return ones[0:K]
            else:
                return ret

    ans = find(0, alls)
    if len(ans):
        a = 0xFFFFFFFFFF
        for p in ans:
            a &= int(p, 2)
        return a
    else:
        return 0

if __name__ == "__main__":
    l = input()
    N = int(l.split(" ")[0])
    K = int(l.split(" ")[1])
    As = [int(c) for c in input().split()]
    print(solve(N, K, As))


Fixed submission:
def solve(N, K, As):
    alls = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            alls.append("{:041b}".format(sum(As[i:j])))
    def find(i, alls):
        if i > 40:
            return []
        ones = [a for a in alls if a[i] == "1"]
        if len(ones) < K:
            return find(i + 1, alls)
        elif len(ones) == K:
            return ones
        elif len(ones) > K:
            ret = find(i + 1, ones)
            if len(ret) == 0:
                return ones[0:K]
            else:
                return ret

    ans = find(0, alls)
    if len(ans):
        a = 0xFFFFFFFFFFF
        for p in ans:
            a &= int(p, 2)
        return a
    else:
        return 0

if __name__ == "__main__":
    l = input()
    N = int(l.split(" ")[0])
    K = int(l.split(" ")[1])
    As = [int(c) for c in input().split()]
    print(solve(N, K, As))
Buggy python submission (verdict: Runtime Error):
def solve(N, M, PYs):
    Ys = {i + 1: 1 for i in range(M)}
    ret = {}
    for p, y in sorted(PYs, key=lambda x: x[1]):
        ret[(p, y)] = "{:06d}{:06d}".format(p, Ys[p])
        Ys[p] += 1
    return [ret[(p, y)] for (p, y) in PYs]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    PYs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print("\n".join(solve(N, M, PYs)))


Fixed submission:
def solve(N, M, PYs):
    Ys = {i + 1: 1 for i in range(N)}
    ret = {}
    for p, y in sorted(PYs, key=lambda x: x[1]):
        ret[(p, y)] = "{:06d}{:06d}".format(p, Ys[p])
        Ys[p] += 1
    return [ret[(p, y)] for (p, y) in PYs]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    PYs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print("\n".join(solve(N, M, PYs)))
Buggy python submission (verdict: Runtime Error):
from collections import Counter


def solve(V):
    n = len(V)
    odd = Counter()
    even = Counter()
    total = Counter()
    for i, c in enumerate(V):
        total.update([c])
        if i % 2 == 0:
            even.update([c])
        else:
            odd.update([c])

    total_max = total.most_common()[0]
    if total_max[1] == len(V):
        return len(V) / 2

    even_maxs = even.most_common(2)
    odd_maxs = odd.most_common(2)
    if len(odd_maxs) > 1:
        odd_max, odd_2nd_max = odd_maxs[0], odd_maxs[1]
    else:
        odd_max, odd_2nd_max = odd_maxs[0], None

    if len(even_maxs) > 1:
        even_max, even_2nd_max = even_maxs[0], even_maxs[1]
    else:
        even_max, even_2nd_max = even_maxs[0], None

    ans = 0
    if odd_max[0] != even_max[0]:
        odd_max = odd_max[0]
        even_max = even_max[0]
    elif odd_2nd_max != None and even_2nd_max == None:
        even_max = even_max[0]
        odd_max = odd_2nd_max[0]
    elif odd_2nd_max == None and even_2nd_max != None:
        odd_max = odd_max[0]
        even_max = even_2nd_max[0]
    else:  # odd_2nd_max != None and even_2nd_max != None:
        return n - max(even_maxs[0][1] + odd_maxs[1][1], 
                       even_maxs[1][1] + odd_maxs[0][1])

    for key, count in even.items():
        if key != even_max:
            ans += count
    for key, count in odd.items():
        if key != odd_max:
            ans += count
    return ans


if __name__ == "__main__":
    n = int(input())
    l = input()
    print(solve(l.split(" ")))


Fixed submission:
def solve(N):
    return l.replace("1", "8").replace("9", "1").replace("8", "9")

if __name__ == "__main__":
    l = input()
    print(solve(l))
Buggy python submission (verdict: Runtime Error):
from collections import Counter


def solve(V):
    n = len(V)
    odd = Counter(V[1::2])
    even = Counter(V[::2])

    even_max = even.most_common(2)
    odd_max = odd.most_common(2)

    if odd_max[0][0] != even_max[0][0]:
        return n - odd_max[0][0] - even_max[0][0]
    elif len(odd_max[0][0]) != 1 and len(even_max[0][0]) == 1:
        return n - odd_max[1][0] - even_max[0][1]
    elif len(odd_max[0][0]) == 1 and len(even_max[0][0]) != 1:
        return n - odd_max[0][1] - even_max[1][1]
    else:
        return n - max(even_max[0][1] + odd_max[1][1],
                       even_max[1][1] + odd_max[0][1])

if __name__ == "__main__":
    n = int(input())
    l = input()
    print(solve(l.split(" ")))


Fixed submission:
import collections
 
n = int(input())
v = list(map(int, input().split()))
a = v[::2]
b = v[1::2]
ac = collections.Counter(a).most_common(2)
bc = collections.Counter(b).most_common(2)
if ac[0][0] != bc[0][0]:
    print(n - ac[0][1] - bc[0][1])
else:
    if len(ac) == 1:
        print(n // 2)
    else:
        print(n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1]))

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


def solve(V):
    n = len(V)
    odd = Counter()
    even = Counter()
    total = Counter()
    for i, c in enumerate(V):
        total.update([c])
        if i % 2 == 0:
            even.update([c])
        else:
            odd.update([c])

    total_max = total.most_common()[0]
    if total_max[1] == len(V):
        return len(V) / 2

    even_maxs = even.most_common(2)
    odd_maxs = odd.most_common(2)
    if len(odd_maxs) > 1:
        odd_max, odd_2nd_max = odd_maxs[0], odd_maxs[1]
    else:
        odd_max, odd_2nd_max = odd_maxs[0], None

    if len(even_maxs) > 1:
        even_max, even_2nd_max = even_maxs[0], even_maxs[1]
    else:
        even_max, even_2nd_max = even_maxs[0], None

    ans = 0
    if odd_max[0] != even_max[0]:
        return n - odd_maxs[0][0] - even_maxs[0][0]
    elif odd_2nd_max != None and even_2nd_max == None:
        return n - odd_maxs[1][0] - even_maxs[0][1]
    elif odd_2nd_max == None and even_2nd_max != None:
        return n - odd_maxs[0][1] - even_maxs[1][1]
    else:  # odd_2nd_max != None and even_2nd_max != None:
        return n - max(even_maxs[0][1] + odd_maxs[1][1], 
                       even_maxs[1][1] + odd_maxs[0][1])

    for key, count in even.items():
        if key != even_max:
            ans += count
    for key, count in odd.items():
        if key != odd_max:
            ans += count
    return ans


if __name__ == "__main__":
    n = int(input())
    l = input()
    print(solve(l.split(" ")))


Fixed submission:
import collections
 
n = int(input())
v = list(map(int, input().split()))
a = v[::2]
b = v[1::2]
ac = collections.Counter(a).most_common(2)
bc = collections.Counter(b).most_common(2)
if ac[0][0] != bc[0][0]:
    print(n - ac[0][1] - bc[0][1])
else:
    if len(ac) == 1:
        print(n // 2)
    else:
        print(n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1]))