Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)

    l = 0
    r = A[-1] * F[0]
    while r != l:
        t = l + (r - l) // 2
        if K >= sum(a - t // f for a, f in zip(A, F) if a * f > t):
            r = t
        else:
            l = t + 1
    print(r)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)
    def helper(t):
        k = K
        for a, f in zip(A, F):
            if a * f <= t:
                continue
            m = t // f
            k -= (a - m)
            if k < 0:
                return False
        return True

    l = 0
    r = A[-1] * F[0]
    while r != l:
        m = l + (r - l) // 2
        if helper(m):
            r = m
        else:
            l = m + 1
    print(r)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)
    def helper(t):
        k = K
        for a, f in zip(A, F):
            if a * f <= t:
                continue
            m = t // f
            k -= (a - m)
            if k < 0:
                return False
        return True

    l = 0
    r = A[-1] * F[0]
    while r != l:
        m = l + (r - l) // 2
        if helper(m):
            r = m
        else:
            l = m + 1
    print(r)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N, K = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()), reverse=True)
    def helper(t):
        k = K
        for a, f in zip(A, F):
            if a * f <= t:
                continue
            m = t // f
            k -= (a - m)
            if k < 0:
                return False
        return True

    l = 0
    r = A[-1] * F[0]
    while r != l:
        m = l + (r - l) // 2
        if helper(m):
            r = m
        else:
            l = m + 1
    print(r)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    t = 0
    for ai, a in enumerate(L):
        hi = ai + 1
        for bi, b in enumerate(L[ai + 1:], ai + 1):
            ab = a + b
            lo = hi
            hi = len(L) - 1
            while lo != hi:
                mid = (lo + hi + 1) // 2
                if L[mid] < ab:
                    lo = mid
                else:
                    hi = mid - 1
            t += hi - bi
    print(t)


main()


Fixed submission:
import bisect

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    t = 0
    l = len(L) - 1
    for ai, a in enumerate(L):
        ci = ai + 1
        for bi, b in enumerate(L[ai + 1:], ai + 1):
            ci = bisect.bisect_left(L, a + b, ci) - 1
            t += ci - bi
    print(t)


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    t = 0
    for ai, a in enumerate(L):
        for bi, b in enumerate(L[ai + 1:], ai + 1):
            ab = a + b
            lo = bi
            hi = len(L) - 1
            while lo != hi:
                mid = (lo + hi + 1) // 2
                if L[mid] < ab:
                    lo = mid
                else:
                    hi = mid - 1
            t += hi - bi
    print(t)


main()


Fixed submission:
import bisect

def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    t = 0
    l = len(L) - 1
    for ai, a in enumerate(L):
        ci = ai + 1
        for bi, b in enumerate(L[ai + 1:], ai + 1):
            ci = bisect.bisect_left(L, a + b, ci) - 1
            t += ci - bi
    print(t)


main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    cd = {}
    FAIL = (10 ** 3) * (10 ** 5) + 1
    for _ in range(M):
        ai, _ = map(int, input().split())
        ci = sum(1 << (int(i) - 1) for i in input().split())
        keys = list(cd.keys())
        for i in keys:
            cd[i | ci] = min(cd.get(i | ci, FAIL), cd[i] + ai)
        cd[ci] = min(cd.get(ci, FAIL), ai)
    print(cd.get((1 << N) - 1, -1))


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
from __future__ import division
def main():
    N = int(input())
    print(1 - ((N // 2) / N))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

import math
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

def fact(n):
    r = [1]
    if n % 2 == 0:
        r.append(2)
    while n % 2 == 0:
        n = n // 2
    i = 3
    while i < n:
        if n % i == 0:
            r.append(i)
        while n % i == 0:
            n = n // i
        i += 2
    if n not in r:
        r.append(n)
    return r

def main():
    A, B = map(int, input().split())
    cf = []
    t = gcd(A, B)
    if t % 2 == 0:
        cf.append(2)
    print(len(fact(t)))


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3

import math
def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x

def fact(n):
    r = [1]
    if n % 2 == 0:
        r.append(2)
        while n % 2 == 0:
            n //= 2
    i = 3
    k = int(math.sqrt(n))
    while i <= k:
        if n % i == 0:
            r.append(i)
            while n % i == 0:
                n //= i
            k = int(math.sqrt(n))
        i += 2
    if n > 1:
        r.append(n)
    return r

def main():
    A, B = map(int, input().split())
    t = gcd(A, B)
    print(len(fact(t)))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3

def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

def main():
    A, B = map(int, input().split())
    cf = []
    if A % 2 == 0 and B % 2 == 0:
        cf.append(2)
    cf.extend(i for i in range(3, int(min(A, B)), 2) if A % i == 0 and B % i == 0)
    a = []
    for i in cf:
        for j in a:
            if gcd(i, j) != 1:
                break
        else:
            a.append(i)
    print(len(a) + 1)




if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3

import math
def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x

def fact(n):
    r = [1]
    if n % 2 == 0:
        r.append(2)
        while n % 2 == 0:
            n //= 2
    i = 3
    k = int(math.sqrt(n))
    while i <= k:
        if n % i == 0:
            r.append(i)
            while n % i == 0:
                n //= i
            k = int(math.sqrt(n))
        i += 2
    if n > 1:
        r.append(n)
    return r

def main():
    A, B = map(int, input().split())
    t = gcd(A, B)
    print(len(fact(t)))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, M = map(int, input().split())
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        V[a - 1].append(b - 1)
    C = [0] * N
    loop = []
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            loop.append(n)
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                loop.append(n)
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            break
    if len(loop) == 0:
        print('-1')
        return
    for i in range(1, len(loop)):
        if loop[i] == loop[0]:
            break
    loop = loop[:i][::-1]

    def minimize(l):
        s = set(l)
        for i in range(len(l)):
            for j in V[l[i]]:
                if j == l[(i + 1) % len(l)]:
                    continue
                if j in s:
                    break
            else:
                continue
            break
        else:
            return l
        I = {m: k for k, m in enumerate(l)}
        j = I[j]
        if i < j:
            l = l[0:i + 1] + l[j:]
        else:
            l = l[j:i + 1]
        return l
    while True:
        t = len(loop)
        loop = minimize(loop)
        if len(loop) == t:
            break
    print(t)
    print('\n'.join(str(i + 1) for i in loop))
main()


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

def main():
    N, M = map(int, input().split())
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        V[a - 1].append(b - 1)
    C = [0] * N
    loop = []
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            loop.append(n)
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                loop.append(n)
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            break
    if len(loop) == 0:
        print('-1')
        return
    for i in range(1, len(loop)):
        if loop[i] == loop[0]:
            break
    loop = loop[:i][::-1]

    def minimize(l):
        s = set(l)
        for i in range(len(l)):
            for j in V[l[i]]:
                if j == l[(i + 1) % len(l)]:
                    continue
                if j in s:
                    break
            else:
                continue
            break
        else:
            return l
        I = {m: k for k, m in enumerate(l)}
        j = I[j]
        if i < j:
            l = l[0:i + 1] + l[j:]
        else:
            l = l[j:i + 1]
        return l
    while True:
        t = len(loop)
        loop = minimize(loop)
        if len(loop) == t:
            break
    print(t)
    print('\n'.join(str(i + 1) for i in loop))
main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    S = input()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    r = 0
    for i in reversed(range(N)):
        s = S[i]
        for j in reversed(range(i, N)):
            if s == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            r = max(r, min(dp[i][j], j - i))
    print(r)

main()


Fixed submission:
def main():
    N = int(input())
    S = input()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    r = 0
    for i in reversed(range(N)):
        s = S[i]
        for j in reversed(range(i, N)):
            if s == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            r = max(r, min(dp[i][j], j - i))
    print(r)

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort(key=lambda x: -x[1])
    M += 1
    w = [False] * M
    r = 0
    c = 0
    for a, b in AB:
        for i in reversed(range(M - a)):
            if w[i]:
                continue
            w[i] = True
            r += b
            c += 1
            break
    return r

print(main())


Fixed submission:
import heapq

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    AB.sort()
    AB.reverse()
    M += 1
    w = [False] * M
    q = []
    r = 0
    for i in range(1, M):
        while AB and AB[-1][0] <= i:
            heapq.heappush(q, -AB.pop()[1])
        if q:
            r += heapq.heappop(q)
    return -r

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    MOD = 10 ** 9 + 7
    S = input()
    u = [1] + [0] * 12
    v = [0] * 13
    m = 1
    shift = 0
    for s in reversed(S):
        if s == '?':
            for j in range(13):
                v[j] = sum(u[(j - (m * i) % 13) % 13] for i in range(10)) % MOD
            u, v = v, u
        else:
            shift = (shift + m * int(s)) % 13
        m = m * 10 % 13
    return u[(5 - shift) % 13]

print(main())


Fixed submission:
def main():
    MOD = 10 ** 9 + 7
    S = input()
    u = [1] + [0] * 12
    v = [0] * 13
    m = 1
    shift = 0
    for s in reversed(S):
        if s == '?':
            for j in range(13):
                v[j] = sum(u[(j - (m * i) % 13) % 13] for i in range(10)) % MOD
            u, v = v, u
        else:
            shift = (shift + m * int(s)) % 13
        m = m * 10 % 13
    return u[(5 - shift) % 13]

print(main())
Buggy python submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    Nodes = [set() for _ in range(N)]
    MOD = 10 ** 9 + 7
    for i in range(N - 1):
        a, b = map(int, input().split())
        Nodes[a - 1].add(b - 1)
        Nodes[b - 1].add(a - 1)
    def helper(n, k, f):
        l = len(Nodes[n])
        r = (K - k) 
        j = 1 if k == 0 else 2
        for i in Nodes[n]:
            if i == f:
                continue
            r = r * helper(i, j, n) % MOD
            j += 1
        return r
    for i in range(N):
        if len(Nodes[i]) == 1:
            break
    return helper(i, 0, -1)

print(main())


Fixed submission:
import sys
sys.setrecursionlimit(10**6)
def main():
    N, K = map(int, input().split())
    Nodes = [set() for _ in range(N)]
    MOD = 10 ** 9 + 7
    for i in range(N - 1):
        a, b = map(int, input().split())
        Nodes[a - 1].add(b - 1)
        Nodes[b - 1].add(a - 1)
    def helper(n, k, f):
        l = len(Nodes[n])
        r = (K - k) 
        j = 1 if k == 0 else 2
        for i in Nodes[n]:
            if i == f:
                continue
            r = r * helper(i, j, n) % MOD
            j += 1
        return r
    for i in range(N):
        if len(Nodes[i]) == 1:
            break
    return helper(i, 0, -1)

print(main())
Buggy python submission (verdict: Runtime Error):
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    mod = 10 ** 9 + 7
    nCr = nCrMod(mod)
    N, K = map(int, input().split())
    r = 0
    for i in range(1, K + 1):
        print(nCr(K - 1, i - 1) * nCr(N - K + 1, i) % mod)
main()


Fixed submission:
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    mod = 10 ** 9 + 7
    nCr = nCrMod(mod)
    N, K = map(int, input().split())
    r = 0
    for i in range(1, K + 1):
        if i - 1 > N - K:
            print(0)
            continue
        print(nCr(K - 1, i - 1) * nCr(N - K + 1, i) % mod)
main()
Buggy python submission (verdict: Runtime Error):
from math import factorial
from itertools import combinations, islice

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    N, K = map(int, input().split())
    A = nCr(N - 1, 2)
    if K > A:
        print(-1)
        return
    print(N - 1 + A - K)
    for i in range(2, N + 1):
        print(1, i)
    for u, v in islice(combinations(list(range(2, N + 1)), 2), A - K):
        print(u, v)

main()


Fixed submission:
from math import factorial
from itertools import combinations, islice

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    N, K = map(int, input().split())
    A = nCr(N - 1, 2) if N > 2 else 0
    if K > A:
        print(-1)
        return
    print(N - 1 + A - K)
    for i in range(2, N + 1):
        print(1, i)
    for u, v in islice(combinations(range(2, N + 1), 2), A - K):
        print(u, v)

main()

Buggy python submission (verdict: Runtime Error):
from math import factorial
from itertools import combinations

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    N, K = map(int, input().split())
    A = nCr(N - 1, 2)
    if K > A:
        print(-1)
        return
    print(N - 1 + A - K)
    for i in range(2, N + 1):
        print(1, i)
    for u, v in list(combinations(list(range(2, N + 1)), 2))[:A - K]:
        print(u, v)

main()


Fixed submission:
from math import factorial
from itertools import combinations, islice

def nCr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    N, K = map(int, input().split())
    A = nCr(N - 1, 2) if N > 2 else 0
    if K > A:
        print(-1)
        return
    print(N - 1 + A - K)
    for i in range(2, N + 1):
        print(1, i)
    for u, v in islice(combinations(range(2, N + 1), 2), A - K):
        print(u, v)

main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    L = [(0, [])]
    R = [(0, [])]

    mp = 0
    mn = []
    for k in range(K):
        if k == len(V):
            break
        v = V[k]
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        L.append((mp, tuple(mn)))

    mp = 0
    mn = []
    for k in range(K):
        i = len(V) - k - 1
        if i < 0:
            break
        v = V[i]
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        R.append((mp, tuple(mn)))

    mval = 0
    for l in range(K + 1):
        if l == len(L) + 1:
            break
        lp, ln = L[l]
        for r in range(K - l):
            if l + r == len(V) or r == len(R) + 1:
                break
            rp, rn = R[r]
            val = rp + lp
            n = K - l - r
            if len(ln) + len(rn) > n:
                t = list(ln) + list(rn)
                t.sort()
                val += sum(t[n:])
            mval = max(mval, val)
    print(mval)


main()


Fixed submission:
def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    L = [(0, [])]
    R = [(0, [])]

    mp = 0
    mn = []
    for _, v in zip(range(K), V):
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        L.append((mp, tuple(mn)))

    mp = 0
    mn = []
    for _, v in zip(range(K), reversed(V)):
        if v >= 0:
            mp += v
        else:
            mn.append(v)
            mn.sort()
        R.append((mp, tuple(mn)))

    mval = 0
    for l, (lp, ln) in enumerate(L):
        for r, (rp, rn) in zip(range(K - l + 1), R):
            if l + r > len(V):
                break
            val = rp + lp
            n = K - l - r
            if len(ln) + len(rn) > n:
                t = list(ln) + list(rn)
                t.sort()
                val += sum(t[n:])
            mval = max(mval, val)
    print(mval)


main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Ap = sorted([i for i in A if i >= 0])
    An = sorted([i for i in A if i < 0])
    if len(An) % 2 == 0:
      return sum(Ap) - sum(An)
    return sum(Ap) - sum(An) - 2 * min(Ap[0], -An[-1])
print(main())



Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    s = sum(abs(a) for a in A)
    if sum(1 for i in A if i < 0) & 1:
        s -= 2 * min(abs(a) for a in A)
    return s

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = sorted(map(int, input().split()), reverse=True)
    AB = sorted((a + b for a in A for b in B), reverse=True)
    def helper(x):
        r = 0
        t = len(C) - 1
        for ab in AB:
            while t >= 0 and C[t] + ab < x:
                t -= 1
            r += t + 1
        return r >= K
    l = binsearch(AB[-1] + C[-1], AB[0] + C[0] + 1, helper)
    r = []
    for ab in AB:
        for c in C:
            if ab + c < l:
                break
            r.append(ab + c)
            if len(r) == K:
                break
        if len(r) >= K:
            break

    r.sort(reverse=True)
    print('\n'.join(str(i) for i in r))

main()





Fixed submission:
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = sorted(map(int, input().split()), reverse=True)
    AB = sorted((a + b for a in A for b in B), reverse=True)
    def helper(x):
        r = 0
        t = len(C) - 1
        for ab in AB:
            while t >= 0 and C[t] + ab < x:
                t -= 1
            r += t + 1
            if r >= K:
                return True
            if t < 0:
                return False
        return r >= K
    l = binsearch(AB[-1] + C[-1], AB[0] + C[0] + 1, helper)
    r = []
    t = len(C) - 1
    for ab in AB:
        while t >= 0 and C[t] + ab < l + 1:
            t -= 1
        if t < 0:
            break
        r.extend(ab + c for c in C[:t + 1])
    r.sort(reverse=True)
    r += [l] * (K - len(r))
    print('\n'.join(str(i) for i in r))

main()
Buggy python submission (verdict: Runtime Error):
def main():
    nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    As = {}
    for a in A:
        As[nums[a]] = max(a, As.get(nums[a], 0))
    A = sorted(list(As.values()), key=lambda x: nums[x])
    def helper(n, A):
        if n == 0:
            return []
        if n < 0:
            return None
        for i in A:
            s = helper(n - nums[i], A)
            if s is None:
                continue
            return s + [i]
        return None
            
    print(''.join(str(i) for i in sorted(helper(N, A), reverse=True)))

main()


Fixed submission:
def main():
    C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] + [-1] * N
    K = {a: C[a - 1] for a in A}

    for i in range(min(K.values()), N + 1):
        try:
            dp[i] = max(dp[i - v] * 10 + k for k, v in K.items() if i - v >= 0 and dp[i - v] >= 0)
        except ValueError:
            dp[i] = -1
    print(dp[N])
main()