Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, S: str):
    d = []  # type: List[int]
    i = 0
    while True:
        r = 0
        while i < N and S[i] == "1":
            r += 1
            i += 1
        d.append(r)
        if i >= N:
            break
        s = 0
        while i < N and S[i] == "0":
            s += 1
            i += 1
        d.append(s)
    c = 2 * K + 1
    if c > len(d):
        print(sum(d))
        return
    print(max(sum(d[dl:dl + c]) for dl in range(0, len(d) - c + 1, 2)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, K: int, S: str):
    d = []  # type: List[int]
    i = 0
    while True:
        r = 0
        while i < N and S[i] == "1":
            r += 1
            i += 1
        d.append(r)
        if i >= N:
            break
        s = 0
        while i < N and S[i] == "0":
            s += 1
            i += 1
        d.append(s)
    c = 2 * K + 1
    if c > len(d):
        print(sum(d))
        return
    dl = 0
    acc = sum(d[:c])
    ans = acc
    while dl + c + 2 <= len(d):
        acc += d[dl + c] + d[dl + c + 1] - d[dl] - d[dl + 1]
        ans = max(ans, acc)
        dl += 2
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n, q = [int(x) for x in input().split()]
s = input()
for i in range(q):
    l, r = [int(x) for x in input().split()]
    print(s[l - 1:r].count("AC"))


Fixed submission:
n, q = [int(x) for x in input().split()]
s = input()
c = [s[i:i + 2] == "AC" for i in range(n - 1)]
d = [0] * n
for i in range(1, n):
    d[i] = d[i - 1] + c[i - 1]

for i in range(q):
    l, r = [int(x) for x in input().split()]
    print(d[r - 1] - d[l - 1])
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys


def solve(S: str):
    nS = len(S)
    pS = ""
    while pS != S:
        pS = S
        S = S.replace("01", "")
        S = S.replace("10", "")
    print(nS - len(S))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()


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


def solve(S: str):
    print(min(S.count("0"), S.count("1")) * 2)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    uf = list(range(N))
    n = [1] * N

    def getpar(a: int):
        if a == uf[a]:
            return a
        uf[a] = getpar(uf[a])
        return uf[a]

    def union(a: int, b: int):
        pa = getpar(a)
        pb = getpar(b)
        if pa == pb:
            return 0, 0
        ra = n[pa]
        rb = n[pb]
        n[pa] += n[pb]
        uf[pb] = uf[pa]
        return ra, rb

    k = N * (N - 1) // 2
    ans = []
    A.reverse()
    B.reverse()
    for Ai, Bi in zip(A, B):
        Ai -= 1
        Bi -= 1
        ra, rb = union(Ai, Bi)
        ans.append(k)
        k -= ra * rb

    assert k == 0, k
    for ansi in reversed(ans):
        print(ansi)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


sys.setrecursionlimit(1000000)


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    uf = list(range(N))
    n = [1] * N

    def getpar(a: int):
        if a == uf[a]:
            return a
        uf[a] = getpar(uf[a])
        return uf[a]

    def union(a: int, b: int):
        pa = getpar(a)
        pb = getpar(b)
        if pa == pb:
            return 0, 0
        ra = n[pa]
        rb = n[pb]
        n[pa] += n[pb]
        uf[pb] = uf[pa]
        return ra, rb

    k = N * (N - 1) // 2
    ans = []
    A.reverse()
    B.reverse()
    for Ai, Bi in zip(A, B):
        Ai -= 1
        Bi -= 1
        ra, rb = union(Ai, Bi)
        ans.append(k)
        k -= ra * rb

    assert k == 0, k
    for ansi in reversed(ans):
        print(ansi)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
try:
    from typing import Dict, List
except ImportError:
    pass


def solve(N: int, M: int, A: "List[int]"):
    mn = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort(reverse=True)
    dp = [-1] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        m = -1
        for Ai in A:
            if i - mn[Ai] >= 0 and dp[i - mn[Ai]] >= 0:
                m = max(m, dp[i - mn[Ai]] + 1)
        if m >= 0:
            dp[i] = m
    assert dp[N] >= 0
    k = N
    res = []  # type: List[int]
    while dp[k]:
        for Ai in A:
            if dp[k - mn[Ai]] == dp[k] - 1:
                res.append(Ai)
                k -= mn[Ai]
                break

    print("".join(str(d) for d in res))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
try:
    from typing import Dict, List
except ImportError:
    pass


def solve(N: int, M: int, A: "List[int]"):
    mn = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort(reverse=True)
    dp = [-1] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        m = -1
        for Ai in A:
            if i - mn[Ai] >= 0 and dp[i - mn[Ai]] >= 0:
                m = max(m, dp[i - mn[Ai]] + 1)
        if m >= 0:
            dp[i] = m
    assert dp[N] >= 0
    k = N
    res = []  # type: List[int]
    while dp[k]:
        for Ai in A:
            if k - mn[Ai] >= 0 and dp[k - mn[Ai]] == dp[k] - 1:
                res.append(Ai)
                k -= mn[Ai]
                break

    print("".join(str(d) for d in res))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
from itertools import product
import sys

try:
    from typing import Dict, List, Tuple
except ImportError:
    pass


MOD = 1000000007  # type: int


def isvalid(ptn: "Tuple[bool]"):
    return not any(h1 and h2 for h1, h2 in zip(ptn, ptn[1:]))


def solve(H: int, W: int, K: int):
    validptns: "List[Tuple[bool]]" = [
        ptn
        for ptn in product((False, True), repeat=W - 1)
        if isvalid(ptn)
    ]
    dp: "List[int]" = [1 if i == K - 1 else 0 for i in range(W)]
    for _ in range(H):
        newdp: "List[int]" = [0] * W
        for ptn in validptns:
            for s in range(W):
                t = s
                if s < W - 1 and ptn[s]:
                    t = s + 1
                elif s > 0 and ptn[s - 1]:
                    t = s - 1
                newdp[t] += dp[s]
                newdp[t] %= MOD
        dp = newdp

    print(dp[0])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(H, W, K)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
from itertools import product
import sys

try:
    from typing import List, Tuple
except ImportError:
    pass


MOD = 1000000007  # type: int


def isvalid(ptn: "Tuple[bool]"):
    return not any(h1 and h2 for h1, h2 in zip(ptn, ptn[1:]))


def solve(H: int, W: int, K: int):
    validptns = [
        ptn
        for ptn in product((False, True), repeat=W - 1)
        if isvalid(ptn)
    ]  # type: List[Tuple[bool]]
    dp = [1 if i == K - 1 else 0 for i in range(W)]  # type: List[int]
    for _ in range(H):
        newdp = [0] * W  # type: List[int]
        for ptn in validptns:
            for s in range(W):
                t = s
                if s < W - 1 and ptn[s]:
                    t = s + 1
                elif s > 0 and ptn[s - 1]:
                    t = s - 1
                newdp[t] += dp[s]
                newdp[t] %= MOD
        dp = newdp

    print(dp[0])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(H, W, K)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, X: int, Y: int, x: "List[int]", y: "List[int]"):
    xs = {X, *x}
    ys = {Y, *y}
    x1 = min(xs)
    x2 = max(xs)
    y1 = min(ys)
    y2 = max(ys)
    print("No War" if (x2 < y1 or y2 < x1) else "War")


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    y = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, X, Y, x, y)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, X: int, Y: int, x: "List[int]", y: "List[int]"):
    xs = set(x)
    xs.add(X)
    ys = set(y)
    ys.add(Y)
    x1 = min(xs)
    x2 = max(xs)
    y1 = min(ys)
    y2 = max(ys)
    print("No War" if (x2 < y1 or y2 < x1) else "War")


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    x = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    y = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, X, Y, x, y)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


class BIT:
    def __init__(self, n: int):
        self.tr = [0] * (n + 1)

    def add(self, n: int, v: int):
        while n < len(self.tr):
            self.tr[n] += v
            n += n & -n

    def cumsum(self, n: int):
        ans = 0
        while n > 0:
            ans += self.tr[n]
            n -= n & -n
        return ans


def solve(N: int, a: "List[int]"):

    def f(m):
        s = [0] * (N + 1)
        for i, ai in enumerate(a):
            s[i + 1] = s[i] + (-1 if ai < m else 1)
        ms = min(s)
        b = BIT(max(s) - ms + 1)
        t = 0
        for si in s:
            t += b.cumsum(si - ms + 1)
            b.add(si - ms + 1, 1)
        return t >= -(-(N * (N + 1) // 2) // 2)

    lb = 0
    rb = max(a) + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if f(m):
            lb = m
        else:
            rb = m

    print(lb)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


class BIT:
    def __init__(self, n: int):
        self.tr = [0] * (n + 1)

    def add(self, n: int, v: int):
        while n < len(self.tr):
            self.tr[n] += v
            n += n & -n

    def cumsum(self, n: int):
        ans = 0
        while n > 0:
            ans += self.tr[n]
            n -= n & -n
        return ans


def solve(N: int, a: "List[int]"):

    def f(m):
        s = [0] * (N + 1)
        for i, ai in enumerate(a):
            s[i + 1] = s[i] + (-1 if ai < m else 1)
        ms = min(s)
        b = BIT(max(s) - ms + 1)
        t = 0
        for si in s:
            t += b.cumsum(si - ms + 1)
            b.add(si - ms + 1, 1)
        return t >= -(-(N * (N + 1) // 2) // 2)

    lb = 0
    rb = max(a) + 1
    while lb + 1 < rb:
        m = (lb + rb) // 2
        if f(m):
            lb = m
        else:
            rb = m

    print(lb)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
a=raw_input()
if a[0] == "1":
  print "ABD" + int(a[1:]+1-1000)
else:
  print "ABC" + a

Fixed submission:
a=raw_input()
if int(a) >= 1000:
  print "ABD"
else:
  print "ABC"
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
from collections import Counter
import sys

try:
    from typing import Set
except ImportError:
    pass


def f(s: "Set[str]", p: int, i: int):
    bins = Counter(sj[p:p + 1] for sj in s)
    cum = 0
    key = ""
    cnt = 0
    for key, cnt in sorted(bins.items()):
        cum += cnt
        if cum > i:
            break
    else:
        raise IndexError(i)
    new_s = {sj for sj in s if sj[p:p + 1] == key}
    if len(new_s) == 1:
        return list(new_s)[0]
    return f(new_s, p + 1, i - cum + cnt)


def solve(s: str, K: int):
    n = len(s)
    ss = {
        s[i:j]
        for i in range(n)
        for j in range(i + 1, n + 1)
    }
    print(f(ss, 0, K - 1))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)


if __name__ == '__main__':
    main()


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


def solve(s: str, K: int):
    n = len(s)
    ss = {
        s[i:j]
        for i in range(n)
        for j in range(i + 1, min(n + 1, i + K + 1))
    }
    print(sorted(ss)[K - 1])
 

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)


if __name__ == '__main__':
    main()

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


def solve(s: str, K: int):
    n = len(s)
    ss = {
        s[i:j]
        for i in range(n)
        for j in range(i + 1, n + 1)
    }
    print(sorted(ss)[K - 1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)


if __name__ == '__main__':
    main()


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


def solve(s: str, K: int):
    n = len(s)
    ss = {
        s[i:j]
        for i in range(n)
        for j in range(i + 1, min(n + 1, i + K + 1))
    }
    print(sorted(ss)[K - 1])
 

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    solve(s, K)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(H: int, W: int, s: "List[str]"):
    print(YES if all(
        any(
            s[y + dy][x + dx] == "#"
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]
            if 0 <= x + dx < W and 0 <= y + dy < H
        )
        for y in range(H)
        for x in range(W)
        if s[y][x] == "#"
    ) else NO)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(H: int, W: int, s: "List[str]"):
    print(YES if all(
        any(
            s[y + dy][x + dx] == "#"
            for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]
            if 0 <= x + dx < W and 0 <= y + dy < H
        )
        for y in range(H)
        for x in range(W)
        if s[y][x] == "#"
    ) else NO)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: "List[List[int]]"):
    es = [
        (A[i][j], i, j)
        for i in range(N)
        for j in range(i)
    ]
    es.sort(reverse=True)
    ans = 0
    for d, i, j in es:
        for k in range(N):
            if k == i or k == j:
                continue
            nd = A[i][k] + A[k][j]
            if nd < d:
                print(-1)
                return
            if nd == d:
                break
        else:
            ans += d
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: "List[List[int]]"):
    es = [
        (A[i][j], i, j)
        for i in range(N)
        for j in range(i)
    ]
    es.sort(reverse=True)
    ans = 0
    for d, i, j in es:
        for k in range(N):
            if k == i or k == j:
                continue
            nd = A[i][k] + A[k][j]
            if nd < d:
                print(-1)
                return
            if nd == d:
                break
        else:
            ans += d
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()