Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
MOD = int(1e9) + 7


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    sortA = sorted(A)
    sortB = sorted(B)
    for i in range(1, N):
        if sortA[i] == sortA[i-1]:
            print(0)
            return
    for j in range(1, M):
        if sortB[j] == sortB[j-1]:
            print(0)
            return
    retval = 1
    for num in range(N*M, 0, -1):
        icandidates = 0
        jcandidates = 0
        just = 1
        for i in range(N):
            if num == A[i]:
                icandidates = 1
                just = 0
                break
            if num <= A[i]:
                icandidates += 1
        for j in range(M):
            if num == B[j]:
                jcandidates = 1
                just = 0
                break
            if num <= B[j]:
                jcandidates += 1
        retval *= icandidates * jcandidates - (N*M - num) * just
        retval %= MOD

    print(retval)


if __name__ == "__main__":
    main()


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


def binsearch(num, ary):
    left = 0
    right = len(ary)
    while left < right:
        center = (left + right) // 2
        if num <= ary[center]:
            left = center + 1
        else:
            right = center
    return left


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    sortA = sorted(A, reverse=True)
    sortB = sorted(B, reverse=True)
    for i in range(1, N):
        if sortA[i] == sortA[i-1]:
            print(0)
            return
    for j in range(1, M):
        if sortB[j] == sortB[j-1]:
            print(0)
            return
    retval = 1
    for num in range(N*M, 0, -1):
        just = 1
        icandidates = binsearch(num, sortA)
        jcandidates = binsearch(num, sortB)
        if icandidates >= 1 and sortA[icandidates-1] == num:
            icandidates = 1
            just = 0
        if jcandidates >= 1 and sortB[jcandidates-1] == num:
            jcandidates = 1
            just = 0
#        print(icandidates, jcandidates, sortA, num)

        retval *= icandidates * jcandidates - (N*M - num) * just
        retval %= MOD

    print(retval)


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

DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def count(start, S, H, W):
    retval = 0
    q = deque()
    q.append((start[0], start[1], "#"))
    tested = [[False] * W for _ in range(H)]
    while(len(q)):
        i, j, color = q.popleft()
        if tested[i][j]:
            continue
        tested[i][j] = True
        if color == ".":
            retval += 1
        if color == "#":
            ncolor = "."
        else:
            ncolor = "#"
        for d in DIRECTIONS:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni and ni < H and 0 <= nj and nj < W and S[ni][nj] == ncolor:
                q.append((ni, nj, ncolor))
    return retval


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    retval = 0
    for i in range(H):
        for j in range(W):
            if(S[i][j] == "#"):
                retval += count((i, j), S, H, W)
    print(retval)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque

DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def count(start, S, H, W, tested):
    if tested[start[0]][start[1]]:
        return 0
    q = deque()
    q.append((start[0], start[1], "#"))
    white = 0
    black = 0
    while(len(q)):
        i, j, color = q.popleft()
        if tested[i][j]:
            continue
        tested[i][j] = True
        if color == ".":
            white += 1
            ncolor = "#"
        else:  # color == "#":
            black += 1
            ncolor = "."
        for d in DIRECTIONS:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni and ni < H and 0 <= nj and nj < W and S[ni][nj] == ncolor:
                q.append((ni, nj, ncolor))
    return black * white


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    tested = [[False] * W for _ in range(H)]
    retval = 0
    for i in range(H):
        for j in range(W):
            if(S[i][j] == "#"):
                retval += count((i, j), S, H, W, tested)
    print(retval)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input().strip()
    t = input().strip()
    dp = [[""] * (len(t)+1) for _ in range(len(s)+1)]
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + s[i-1]
            if len(dp[i][j]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j]
            if len(dp[i][j]) < len(dp[i][j-1]):
                dp[i][j] = dp[i][j-1]
    print(dp[len(s)][len(t)])


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    s = input().strip()
    t = input().strip()
    dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
    for i in range(1, len(s)+1):
        for j in range(1, len(t)+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            if dp[i][j] < dp[i-1][j]:
                dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
    ans = ""
    i = len(s)
    j = len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i] + ans
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    c = [0] * 4
    for num in map(int, input().split()):
        c[num] += 1
    dp = [[[0] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
    for i3 in range(c[3]+1):
        for i2 in range(c[2]+c[3]-i3+1):
            for i1 in range(c[1]+c[2]+c[3]-i2-i3+1):
                if i1 == i2 == i3 == 0:
                    continue
                tmp = N / (i1+i2+i3)
                if i1 > 0:
                    tmp += i1 * dp[i1-1][i2][i3] / (i1+i2+i3)
                if i2 > 0:
                    tmp += i2 * dp[i1+1][i2-1][i3] / (i1+i2+i3)
                if i3 > 0:
                    tmp += i3 * dp[i1][i2+1][i3-1] / (i1+i2+i3)
                dp[i1][i2][i3] = tmp

    print(dp[c[1]][c[2]][c[3]])


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    c = [0] * 4
    for num in map(int, input().split()):
        c[num] += 1
    dp = [[[0] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
    for i3 in range(c[3]+1):
        for i2 in range(c[2]+c[3]-i3+1):
            for i1 in range(c[1]+c[2]+c[3]-i2-i3+1):
                try:
                    dp[i1][i2][i3] = (i1 * dp[i1-1][i2][i3] +
                                      i2 * dp[i1+1][i2-1][i3] +
                                      i3 * dp[i1][i2+1][i3-1] +
                                      N) / (i1+i2+i3)
                except IndexError:
                    continue
                except ZeroDivisionError:
                    continue

    print(dp[c[1]][c[2]][c[3]])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))

    dp = [[float("inf")]*(N-i+1) for i in range(N+1)]
    dp[1] = [0] * N
    for i in range(2, N+1):
        for j in range(N-i+1):
            for k in range(1, i):
                dp[i][j] = min(dp[k][j] + dp[i-k][j+k] +
                               sum(A[j:j+i]), dp[i][j])
    print(dp[N][0])


if __name__ == "__main__":
    main()


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

    cumsum = [[0]*(N-i+1) for i in range(N+1)]

    dp = [[float("inf")]*(N-i+1) for i in range(N+1)]
    dp[1] = [0] * N
    cumsum[1] = A
    for i in range(2, N+1):
        for j in range(N-i+1):
            cumsum[i][j] = cumsum[i-1][j+1] + A[j]
            for k in range(1, i):
                dp[i][j] = min(dp[k][j] + dp[i-k][j+k] +
                               cumsum[i][j], dp[i][j])
    print(dp[N][0])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heappush


def main():
    N, M, S = map(int, input().split())
    adj = [set() for _ in range(N)]
    for i in range(M):
        x, y = map(int, input().split())
        adj[x-1].add(y-1)
        adj[y-1].add(x-1)
    path = [-1] * N
    q = [(-(S-1), S-1)]
    while len(q):
        minimum, cur = heappop(q)
        minimum = -minimum
        if minimum <= path[cur]:
            continue
        path[cur] = minimum
        for a in adj[cur]:
            heappush(q, (-min(minimum, a), a))
    for i in range(N):
        if path[i] == i:
            print(i+1)


if __name__ == "__main__":
    main()


Fixed submission:
class SegmentTree():
    def __init__(self, values, merge_func=min, default=float("inf")):
        n = len(values)
        self.size = 1
        self.default = default
        self.merge = merge_func
        while self.size < n:
            self.size *= 2
        # tree[0] = empty
        # child of tree[n] = tree[n*2], tree[n*2+1]
        self.tree = [self.default] * self.size * 2
        for i in range(n):
            self.tree[self.size + i] = values[i]
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.merge(self.tree[i*2], self.tree[i*2+1])

    def update(self, index, value):
        index += self.size
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.merge(
                self.tree[index*2], self.tree[index*2+1])

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.default
        if a <= l and r <= b:
            return self.tree[k]
        left = self.__query(a, b, k*2, l, (l+r)//2)
        right = self.__query(a, b, k*2+1, (l+r)//2, r)
        return self.merge(left, right)

    # query segmentation value of [a, b)
    def query(self, a, b):
        return self.__query(a, b, 1, 0, self.size)


def main():
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    RMQ = SegmentTree([0] * N, merge_func=max, default=0)
    for i in range(N):
        maximum = RMQ.query(0, H[i]-1)
        RMQ.update(H[i]-1, maximum + A[i])
    print(RMQ.query(0, N))


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import math
MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    x = int(math.log2(K))
    dp = [[[0] * N for _ in range(N)] for _ in range(x+1)]
    dp[0] = A
    for d in range(x):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[d+1][i][j] = (dp[d+1][i][j] +
                                     dp[d][i][k] * dp[d][k][j]) % MOD
    ans = [1] * N
    for d in range(x+1):
        if K & (2 ** d) == 0:
            continue
        prev = list(ans)
        ans = [0] * N
        for i in range(N):
            for j in range(N):
                ans[j] = (ans[j] + dp[d][i][j] * prev[i]) % MOD

    print(sum(ans) % MOD)


if __name__ == "__main__":
    main()


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


def main():
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    x = int(math.log(K, 2))
    dp = [[[0] * N for _ in range(N)] for _ in range(x+1)]
    dp[0] = A
    for d in range(x):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[d+1][i][j] = (dp[d+1][i][j] +
                                     dp[d][i][k] * dp[d][k][j]) % MOD
    ans = [1] * N
    for d in range(x+1):
        if K & (2 ** d) == 0:
            continue
        prev = list(ans)
        ans = [0] * N
        for i in range(N):
            for j in range(N):
                ans[j] = (ans[j] + dp[d][i][j] * prev[i]) % MOD

    print(sum(ans) % MOD)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    primes = []
    i = 2
    while i**N <= P:
        isprime = True
        for p in primes:
            if i % p == 0:
                isprime = False
                break
        if isprime:
            primes.append(i)
        i += 1

    F = {}
    i = 0
    while P > 1 and i < len(primes):
        factor = primes[i]
        while P % factor == 0:
            if factor not in F:
                F[factor] = 0
            F[factor] += 1
            P //= factor
        i += 1
    retval = 1
    for p in F:
        if F[p] >= N:
            retval *= p
    print(retval)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    if N >= 40:
        print(1)
        return

    i = 2
    retval = 1
    while P > 1 and i**N <= P:
        cnt = 0
        while P % i == 0:
            cnt += 1
            P //= i
        retval *= i ** (cnt // N)
        i += 1
    print(retval)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def count(value, P):
    cnt = 0
    for p in P:
        if p & value == value:
            cnt += 1
    return cnt


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    P = []
    for i in range(N):
        for j in range(i+1, N+1):
            P.append(sum(A[i:j]))
    retval = 0
    for idx in range(40, -1, -1):
        tmp = retval + 2**idx
        if count(tmp, P) >= K:
            retval = tmp
    print(retval)


if __name__ == "__main__":
    main()


Fixed submission:
def count(value, P):
    cnt = 0
    for p in P:
        if p & value == value:
            cnt += 1
    return cnt


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    P = []
    for i in range(N):
        s = 0
        for j in range(i, N):
            s += A[j]
            P.append(s)
    retval = 0
    for idx in range(40, -1, -1):
        tmp = retval + 2**idx
        if count(tmp, P) >= K:
            retval = tmp
    print(retval)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    ans = 0
    edge = [A.pop()] * 2
    while len(A):
        a = abs(edge[0] - A[0])
        b = abs(edge[0] - A[len(A) - 1])
        c = abs(edge[1] - A[0])
        d = abs(edge[1] - A[len(A) - 1])
        if max(a, b, c, d) == a:
            edge[0] = A.pop(0)
            ans += a
        elif max(a, b, c, d) == b:
            edge[0] = A.pop()
            ans += b
        elif max(a, b, c, d) == c:
            edge[1] = A.pop(0)
            ans += c
        else:
            edge[1] = A.pop()
            ans += d
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    ans = 0
    B = deque(A)
    edge = [B.popleft()] * 2
    while len(B):
        a = abs(edge[0] - B[0])
        b = abs(edge[0] - B[len(B) - 1])
        c = abs(edge[1] - B[0])
        d = abs(edge[1] - B[len(B) - 1])
        if max(a, b, c, d) == a:
            edge[0] = B.popleft()
            ans += a
        elif max(a, b, c, d) == b:
            edge[0] = B.pop()
            ans += b
        elif max(a, b, c, d) == c:
            edge[1] = B.popleft()
            ans += c
        else:
            edge[1] = B.pop()
            ans += d
    print(ans)


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

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import math


def main():
    N = int(input())
    x = math.floor(math.sqrt(N*2))
    if x * (x+1) != N*2:
        print("No")
        return
    print("Yes")
    print(x+1)
    s = [[] for _ in range(x+1)]
    counter = 1
    for i in range(x+1):
        for j in range(i+1, x+1):
            s[i].append(counter)
            s[j].append(counter)
            counter += 1
    for i in range(x+1):
        print(len(s[i]), *s[i])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
mod = int(1e9) + 7


def power(x, y):
    if y == 0       : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod


def div(a, b):
    return a * power(b, mod-2) % mod


fact = [1] * int(1e5)
for i in range(1, int(1e5)):
    fact[i] = (i * fact[i-1]) % mod


def combination(n, r):
    return div(div(fact[n], fact[r]), fact[n-r])


def main():
    S = input()
    cumsum_A = [0] * len(S)
    cumsum_B = [0] * len(S)
    cumsum_C = [0] * len(S)
    cumsum_Q = [0] * len(S)
    for i in range(len(S)):
        cumsum_A[i] = cumsum_A[i-1] if i > 0 else 0
        cumsum_B[i] = cumsum_B[i-1] if i > 0 else 0
        cumsum_C[i] = cumsum_C[i-1] if i > 0 else 0
        cumsum_Q[i] = cumsum_Q[i-1] if i > 0 else 0
        s = S[i]
        if s == "A":
            cumsum_A[i] += 1
        if s == "B":
            cumsum_B[i] += 1
        if s == "C":
            cumsum_C[i] += 1
        if s == "?":
            cumsum_Q[i] += 1
    retval = 0
    for i in range(len(S)):
        s = S[i]
        if s == "B" or s == "?":
            a = cumsum_A[i]
            aq = cumsum_Q[i]
            c = cumsum_C[-1] - cumsum_C[i]
            cq = cumsum_Q[-1] - cumsum_Q[i]
            if s == "?":
                aq -= 1
            asum = 0
            for j in range(aq+1):
                asum += (a + j) * power(2, aq-j) * combination(aq, j)
                asum %= mod
            csum = 0
            for j in range(cq+1):
                csum += (c + j) * power(2, cq-j) * combination(cq, j)
                csum %= mod
            retval = (retval + asum * csum) % mod
    print(retval)

if __name__ == "__main__":
    main()


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


def main():
    S = input()
    a_sum = 0
    ab_sum = 0
    abc_sum = 0
    pattern = 1
    for i in range(len(S)):
        s = S[i]
        if s == "A":
            a_sum = (a_sum + pattern) % mod
        if s == "B":
            ab_sum = (ab_sum + a_sum) % mod
        if s == "C":
            abc_sum = (abc_sum + ab_sum) % mod
        if s == "?":
            abc_sum = (abc_sum * 3 + ab_sum) % mod
            ab_sum = (ab_sum * 3 + a_sum) % mod
            a_sum = (a_sum * 3 + pattern) % mod
            pattern = pattern * 3 % mod
    print(abc_sum)


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


def lcm(a, b):
    return a * b // math.gcd(a, b)


def f(n, A):
    return sum([n % x for x in A])


def main():
    N = int(input())
    A = list(map(int, input().split()))
    retval = 1
    for a in A:
        retval = lcm(a, retval)
    print(f(retval - 1, A))


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(sum([x-1 for x in A]))


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


def dijkstra(adj, start):
    ans = [float("inf")] * len(adj)
    q = [(0, start)]
    while len(q):
        cost, node = heapq.heappop(q)
        if cost > ans[node]:
            continue
        ans[node] = cost
        for nxt in adj[node]:
            heapq.heappush(q, (cost + adj[node][nxt], nxt))
    return ans


def main():
    n, m, s, t = map(int, input().split())
    adj1 = [{} for _ in range(n)]
    adj2 = [{} for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        adj1[u-1][v-1] = a
        adj1[v-1][u-1] = a
        adj2[u-1][v-1] = b
        adj2[v-1][u-1] = b
    d1 = dijkstra(adj1, s-1)
    d2 = dijkstra(adj2, t-1)
    ans = [float("inf")] * n
    ans[n-1] = d1[n-1] + d2[n-1]
    for i in range(n-2, -1, -1):
        ans[i] = min(d1[i] + d2[i], ans[i+1])
    for i in range(n):
        print(10**15 - ans[i])


if __name__ == "__main__":
    main()


Fixed submission:
from heapq import heappush, heappop


def dijkstra(N, adj, start=0):
    ans = [float("inf")] * N
    q = [(0, start)]
    while len(q):
        cost, i = heappop(q)
        if ans[i] <= cost:
            continue
        ans[i] = cost
        for nxt in adj[i]:
            if ans[nxt] == float("inf"):
                heappush(q, (cost + adj[i][nxt], nxt))
    return ans


def main():
    n, m, s, t = map(int, input().split())
    adj1 = [{} for _ in range(n)]
    adj2 = [{} for _ in range(n)]
    for _ in range(m):
        u, v, a, b = map(int, input().split())
        adj1[u-1][v-1] = a
        adj1[v-1][u-1] = a
        adj2[u-1][v-1] = b
        adj2[v-1][u-1] = b
    d1 = dijkstra(n, adj1, s-1)
    d2 = dijkstra(n, adj2, t-1)
    ans = [float("inf")] * n
    ans[n-1] = d1[n-1] + d2[n-1]
    for i in range(n-2, -1, -1):
        ans[i] = min(d1[i] + d2[i], ans[i+1])
    for i in range(n):
        print(10**15 - ans[i])


if __name__ == "__main__":
    main()