Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
MOD = int(1e9+7)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * 3
    ans = 1
    for a in A:
        ans = (ans * cnt.count(a)) % MOD
        c = cnt.index(a)
        cnt[c] += 1
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
MOD = int(1e9+7)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * 3
    ans = 1
    for a in A:
        ans = (ans * cnt.count(a)) % MOD
        try:
            c = cnt.index(a)
        except ValueError:
            print(0)
            return
        cnt[c] += 1
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def search(N, M, adj):
    reachable = [[set() for i in range(N)] for _ in range(N)]
    reachable[0] = adj
    start = -1
    for m in range(1, N):
        prev = reachable[m-1]
        cur = reachable[m]
        for i in range(N):
            cur[i] = set(prev[i])
        for i in range(N):
            for nxt in adj[i]:
                if i in prev[nxt]:
                    return (i, reachable, m+1)
                for p in prev[nxt]:
                    cur[i].add(p)
    return None


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
    result = search(N, M, adj)
    if not result:
        print(-1)
        return
    start, reachable, cnt = result
    ans = [-1] * cnt
    x = start
    for i in range(cnt):
        ans[i] = x+1
        for nxt in adj[x]:
            if start in reachable[cnt-i-1][nxt]:
                x = nxt
                break
    print(len(ans))
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


Fixed submission:
def search(N, M, adj):
    reachable = [[set() for i in range(N)] for _ in range(N)]
    reachable[0] = adj
    start = -1
    for m in range(1, N):
        prev = reachable[m-1]
        cur = reachable[m]
        #        for i in range(N):
        #            cur[i] = set(prev[i])
        for i in range(N):
            for nxt in adj[i]:
                for p in prev[nxt]:
                    cur[i].add(p)
                if i in prev[nxt]:
                    return (i, reachable, m+1)
    return None


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
    result = search(N, M, adj)
    if not result:
        print(-1)
        return
    start, reachable, cnt = result
    ans = [-1] * cnt
    x = start
    for i in range(cnt):
        ans[i] = x+1
        for nxt in adj[x]:
            if start in reachable[cnt-i-2][nxt]:
                x = nxt
                break
    print(len(ans))
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def check(S, l):
    for i in range(len(S)-l*2+1):
        x = S[i:i+l]
        if S[i+l:].find(x) != -1:
            return True
    return False


def main():
    N = int(input())
    S = input()
    lo = 0
    hi = N//2
    while lo < hi:
        mid = -(-(lo+hi)//2)
        if check(S, mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    main()


Fixed submission:
def check(S, l):
    idx = {}
    for i in range(len(S)-l+1):
        x = S[i:i+l]
        if x not in idx:
            idx[x] = i
        else:
            if idx[x]+l <= i:
                return True
    return False


def main():
    N = int(input())
    S = input()
    lo = 0
    hi = N//2
    while lo < hi:
        mid = -(-(lo+hi)//2)
        if check(S, mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop


def calc(idx, left, right):
    while -left[0] > idx:
        x = -heappop(left)
        heappush(right, x)
    while right[0] < idx:
        x = heappop(right)
        heappush(left, -x)
    ret = 0
    l = -heappop(left)
    r = heappop(right)
    ret += (right[0] - r) * (idx - l) + \
           (l - (-left[0])) * (r - idx)
    heappush(left, -l)
    heappush(right, r)
    heappush(right, idx)
    return ret


def main():
    N = int(input())
    P = list(map(int, input().split()))
    idx = [0] * N
    for i in range(N):
        idx[P[i]-1] = i
    left = [1, 1]
    right = [N, N]
    ans = 0
    for i in range(N)[::-1]:
        x = calc(idx[i], left, right)
        ans += (i+1) * x
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        lo = -1
        hi = self.N
        while lo < hi:
            mid = (lo+hi)//2
            if self.query(mid) < x:
                lo = mid + 1
            else:
                hi = mid
        return lo


def main():
    N = int(input())
    P = list(map(int, input().split()))
    idx = [0] * N
    bit = BinaryIndexedTree(N)
    for i in range(N):
        idx[P[i]-1] = i
    ans = 0
    for i in range(N)[::-1]:
        bit.add(idx[i], 1)
        x = bit.query(idx[i])
        l = bit.search(x-1)
        ll = bit.search(x-2)
        r = bit.search(x+1)
        rr = bit.search(x+2)
        tmp = (idx[i]-l) * (rr-r) + (r-idx[i]) * (l-ll)
        ans += (i+1) * tmp
    print(ans)


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


def main():
    N, Q = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    cnt = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x
    ans = [0] * N
    q = deque([(0, 0, -1)])
    while len(q):
        cur, total, prev = q.popleft()
        total += cnt[cur]
        ans[cur] = total
        for a in adj[cur]:
            if a == prev:
                continue
            q.append((a, total, cur))
    print(*ans)


if __name__ == "__main__":
    main()


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


def main():
    N, Q = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    cnt = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x
    ans = [0] * N
    q = deque([(0, 0, -1)])
    while len(q):
        cur, total, prev = q.popleft()
        total += cnt[cur]
        ans[cur] = total
        for a in adj[cur]:
            if a == prev:
                continue
            q.append((a, total, cur))
    print(*ans)


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


def check(A, d, K):
    modcnt = [0] * d
    cnt = 0
    for a in A:
        modcnt[a % d] += 1
    mx = d-1
    for i in range(d):
        while modcnt[i] > 0:
            modcnt[i] -= 1
            cnt += i
            pls = i
            while pls > 0:
                while modcnt[mx] == 0 and mx > 1:
                    mx -= 1
                if mx + pls >= d:
                    modcnt[mx] -= 1
                    pls -= d - mx
                else:
                    modcnt[mx] -= 1
                    modcnt[mx+pls] += 1
                    mx = mx+pls
                    pls = 0
    return cnt <= K


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)
    divs = [1, total]
    rt = int(math.sqrt(total))
    for i in range(2, rt+1):
        if total % i == 0:
            divs.append(i)
            if i**2 != total:
                divs.append(total//i)
    ans = 0
    for d in divs:
        if check(A, d, K):
            ans = max(ans, d)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import math
from collections import deque


def check(A, d, K):
    diff = []
    for a in A:
        if a % d != 0:
            diff.append(a % d)
    totalinc = 0
    diff.sort()
    q = deque(diff)
    cnt = 0
    while len(q):
        x = q.popleft()
        cnt += x
        totalinc += x
        while len(q) and q[-1] + totalinc >= d:
            y = q.pop()
            totalinc -= d-y
    cnt += totalinc
    return cnt <= K


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)
    divs = [1, total]
    rt = int(math.sqrt(total))
    for i in range(2, rt+1):
        if total % i == 0:
            divs.append(i)
            if i**2 != total:
                divs.append(total//i)
    ans = 0
    for d in divs:
        if check(A, d, K):
            ans = max(ans, d)
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    idx = [[] for _ in range(int(2e5+1))]
    for i in range(N):
        idx[A[i]].append(i)
    pos = 0
    empty = []
    visited = set()
    while pos == 0 or pos % N != 0:
        empty.append(pos)
        visited.add(pos % N)
        num = A[pos % N]
        nxt = bisect_right(idx[num], pos % N) % len(idx[num])
        npos = idx[num][nxt]
        while npos <= pos:
            npos += N
        pos = npos + 1
    goal = N * K % pos
    cur = empty[max(0, bisect_right(empty, goal) - 1)]
    #print(cur, goal)
    ans = []
    seen = set()
    while cur < goal:
        a = A[cur % N]
        if a not in seen:
            ans += [a]
            seen.add(a)
        else:
            seen.remove(a)
            i = len(ans) - 1
            while i > 0 and ans[i] != a:
                seen.remove(ans[i])
                i -= 1
            ans = ans[:i]
        cur += 1
    print(*ans)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left, bisect_right


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    idx = [[] for _ in range(int(2e5+1))]
    for i in range(N):
        idx[A[i]].append(i)
    pos = 0
    empty = []
    visited = set()
    while pos == 0 or pos % N != 0:
        empty.append(pos)
        visited.add(pos % N)
        a = A[pos % N]
        nxt = bisect_right(idx[a], pos % N) % len(idx[a])
        npos = idx[a][nxt] + (pos//N) * N
        if npos <= pos:
            npos += N
        pos = npos + 1
    goal = N * K % pos
    cur = empty[max(0, bisect_right(empty, goal) - 1)]
    #print(cur, goal)
    ans = []
    seen = set()
    while cur < goal:
        i = cur % N
        a = A[i]
        nxt = bisect_right(idx[a], cur % N) % len(idx[a])
        ncur = idx[a][nxt] + (cur//N) * N
        if ncur <= cur:
            ncur += N
        if ncur < goal:
            cur = ncur + 1
        else:
            ans += [a]
            cur = cur + 1
    print(*ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import math
from bisect import bisect_left

MOD = 10**9 + 7


def main():
    N, K = map(int, input().split())
    R = int(math.sqrt(N))
    if N // R == R:
        M = R * 2 - 1
    else:
        M = R * 2
    mapping = [0] * (M+1)
    for i in range(1, R+1):
        mapping[i] = i
        mapping[-i] = N//i
    cnt = [0] * (M+1)
    for i in range(1, M+1):
        cnt[i] = mapping[i] - mapping[i-1]
    dp = [[0] * (M+1) for _ in range(K+1)]
    dp[0] = list(cnt)
    for i in range(M):
        dp[0][i+1] += dp[0][i]

    for i in range(K-1):
        for j in range(1, M+1):
            v = N // mapping[j]
            idx = bisect_left(mapping, v)
            dp[i+1][j] = dp[i][idx]
        for j in range(M):
            dp[i+1][j+1] = (dp[i+1][j] + dp[i+1][j+1] * cnt[j+1]) % MOD
    print(dp[K-1][M])


if __name__ == "__main__":
    main()


Fixed submission:
import math

MOD = 10**9 + 7


def main():
    N, K = map(int, input().split())
    R = int(math.sqrt(N))
    if N // R == R:
        M = R * 2 - 1
    else:
        M = R * 2
    mapping = [0] * (M+1)
    for i in range(1, R+1):
        mapping[i] = i
        mapping[-i] = N//i
    cnt = [0] * (M+1)
    for i in range(1, M+1):
        cnt[i] = mapping[i] - mapping[i-1]
    dp = [[0] * (M+1) for _ in range(K+1)]
    dp[0] = list(cnt)
    for i in range(M):
        dp[0][i+1] += dp[0][i]

    for i in range(K-1):
        for j in range(1, M+1):
            if j <= R:
                idx = -j
            else:
                idx = M - j + 1
            dp[i+1][j] = dp[i][idx]
        for j in range(M):
            dp[i+1][j+1] = (dp[i+1][j] + dp[i+1][j+1] * cnt[j+1]) % MOD
    print(dp[K-1][M])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    P = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (x, y)
    P.sort()
    cnt = {}
    for i in range(N):
        for j in range(i+1, N):
            ix, iy = P[i]
            jx, jy = P[j]
            d = (jx - ix, jy - iy)
            if d not in cnt:
                cnt[d] = 0
            cnt[d] += 1
    print(N - max(cnt.values()))


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    if N == 1:
        print(1)
        return
    P = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (x, y)
    P.sort()
    cnt = {}
    for i in range(N):
        for j in range(i+1, N):
            ix, iy = P[i]
            jx, jy = P[j]
            d = (jx - ix, jy - iy)
            if d not in cnt:
                cnt[d] = 0
            cnt[d] += 1
    print(N - max(cnt.values()))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def change(N, A, B):
    ans = N
    dp = [[0] * (N+1) for _ in range(4)]
    dp[0] = list(range(N+1))
    for i in range(1, 4):
        w = A[i-1]
        v = B[i-1]
        for j in range(N+1):
            dp[i][j] = dp[i-1][j]
            if w <= j:
                dp[i][j] = max(dp[i][j], dp[i][j-w] + v)

    return dp[3][N]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    N1 = change(N, A, B)
    N2 = change(N1, B, A)
    print(N2)


if __name__ == "__main__":
    main()


Fixed submission:
def change(N, A, B):
    ans = N
    dp = list(range(N+1))
    for i in range(3):
        w = A[i]
        v = B[i]
        for j in range(N+1):
            if w <= j:
                dp[j] = max(dp[j], dp[j-w] + v)
    return dp[N]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    N1 = change(N, A, B)
    N2 = change(N1, B, A)
    print(N2)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    D = [tuple(map(int, input().split())) for _ in range(N)]
    D.sort()
    ans = 0
    while M > 0:
        a, b = D.pop(0)
        ans += a * min(M, b)
        M -= min(M, b)
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N, M = map(int, input().split())
    D = [tuple(map(int, input().split())) for _ in range(N)]
    D.sort()
    ans = 0
    i = 0
    while M > 0:
        a, b = D[i]
        ans += a * min(M, b)
        M -= min(M, b)
        i += 1
    print(ans)


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

INF = float("inf")


def main():
    A, B, Q = map(int, input().split())
    S = [-INF] + [int(input()) for _ in range(A)] + [INF]
    T = [-INF] + [int(input()) for _ in range(B)] + [INF]
    for i in range(Q):
        x = int(input())
        l1 = bisect_left(S, x)
        l2 = bisect_left(T, x)
        tmp = INF
        for s in (S[l1-1], S[l1]):
            for t in (T[l2-1], T[l2]):
                tmp = min(tmp, abs(s-t) + abs(x-s))
                tmp = min(tmp, abs(s-t) + abs(x-t))
        print(tmp)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left

INF = 10**12


def main():
    A, B, Q = map(int, input().split())
    S = [-INF] + [int(input()) for _ in range(A)] + [INF]
    T = [-INF] + [int(input()) for _ in range(B)] + [INF]
    for _ in range(Q):
        x = int(input())
        l1 = bisect_left(S, x)
        l2 = bisect_left(T, x)
        tmp = INF
        for s in (S[l1-1], S[l1]):
            for t in (T[l2-1], T[l2]):
                tmp = min(tmp, abs(s-t) + abs(x-s))
                tmp = min(tmp, abs(s-t) + abs(x-t))
        print(tmp)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def binsearch(left=-1, right=float("inf"), evaluate=lambda: True):
    while left + 1 < right:
        mid = (left + right) // 2
        if evaluate(mid):
            right = mid
        else:
            left = mid
    return left


def binsearch_arr(target, arr):
    return binsearch(evaluate=lambda x: target <= arr[x], left=-1, right=len(arr))


def main():
    A, B, Q = map(int, input().split())
    S = [int(input()) for _ in range(A)]
    T = [int(input()) for _ in range(B)]
    for i in range(Q):
        x = int(input())
        l1 = binsearch_arr(x, S)
        l2 = binsearch_arr(x, T)
        tmp = float("inf")
        if l1 >= 0 and l2 >= 0:
            tmp = min(tmp, x - min(S[l1], T[l2]))
        if l1+1 < len(S) and l2 >= 0:
            tmp = min(tmp, S[l1+1] - T[l2] + min(S[l1+1]-x, x-T[l2]))
        if l1 >= 0 and l2+1 < len(T):
            tmp = min(tmp, T[l2+1] - S[l1] + min(T[l2+1]-x, x-S[l1]))
        if l1+1 < len(S) and l2+1 < len(T):
            tmp = min(tmp, max(S[l1+1], T[l2+1]) - x)
        print(tmp)


if __name__ == "__main__":
    main()


Fixed submission:
from bisect import bisect_left

INF = 10**12


def main():
    A, B, Q = map(int, input().split())
    S = [-INF] + [int(input()) for _ in range(A)] + [INF]
    T = [-INF] + [int(input()) for _ in range(B)] + [INF]
    for _ in range(Q):
        x = int(input())
        l1 = bisect_left(S, x)
        l2 = bisect_left(T, x)
        tmp = INF
        for s in (S[l1-1], S[l1]):
            for t in (T[l2-1], T[l2]):
                tmp = min(tmp, abs(s-t) + abs(x-s))
                tmp = min(tmp, abs(s-t) + abs(x-t))
        print(tmp)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [-1] * (N+1)
    dp[0] = 0
    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    for i in range(N+1):
        for d in A:
            if i < cost[d]:
                continue
            prev = dp[i - cost[d]]
            if prev == -1:
                continue
            elif prev == 0:
                candidate = d
            else:
                candidate = max(int("{}{}".format(prev, d)),
                                int("{}{}".format(d, prev)))
            dp[i] = max(dp[i], candidate)
    print(dp[N])


if __name__ == "__main__":
    main()


Fixed submission:
def strmax(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:
        return max(a, b)


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [None] * (N+1)
    dp[0] = ""
    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    for i in range(N+1):
        for d in A:
            if i < cost[d]:
                continue
            prev = dp[i - cost[d]]
            if prev is None:
                continue
            else:
                candidate = strmax(prev + str(d),
                                   str(d) + prev)
            if dp[i] is None:
                dp[i] = candidate
            else:
                dp[i] = strmax(dp[i], candidate)
    print(dp[N])


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


def main():
    N, M = map(int, input().split())
    parents = [[] for _ in range(N+1)]
    childs = [[] for _ in range(N+1)]
    for i in range(N+M-1):
        a, b = map(int, input().split())
        childs[a].append(b)
        parents[b].append(a)
    root = -1
    for i in range(1, N+1):
        if len(parents[i]) == 0:
            root = i
            break
    originalParent = [-1] * (N+1)
    q = deque([])
    q.append((root, 0))
    while(len(q)):
        n, parent = q.popleft()
        originalParent[n] = parent
        for c in childs[n]:
            q.append((c, n))
    for i in range(1, N+1):
        print(originalParent[i])


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque, defaultdict


def main():
    N, M = map(int, input().split())
    childs = defaultdict(list)
    parents = defaultdict(int)
    for i in range(N+M-1):
        a, b = map(int, input().split())
        childs[a].append(b)
        parents[b] += 1
    q = deque(x for x in range(1, N+1) if parents[x] == 0)
    ans = defaultdict(int)
    while(len(q)):
        n = q.popleft()
        for c in childs[n]:
            parents[c] -= 1
            if parents[c] == 0:
                q.append(c)
                ans[c] = n
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    main()