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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = in_nl()

    mod = 10**9 + 7
    num = [0] * 3
    ans = 1

    for i in range(N):
        min_j = 4
        count = 0
        for j in range(3):
            if num[j] == A[i]:
                count += 1
                min_j = min(min_j, j)
        num[min_j] += 1
        ans *= count
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = in_nl()

    mod = 10**9 + 7
    num = [0] * 3
    ans = 1

    for i in range(N):
        min_j = 4
        count = 0
        for j in range(3):
            if num[j] == A[i]:
                count += 1
                min_j = min(min_j, j)
        if min_j == 4:
            ans = 0
            break
        num[min_j] += 1
        ans *= count
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    # print(ab)
    # print(edge)

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    # print(max_v)
    # print(max_v_dim)

    # bfs
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = np.full((N, N), -1, dtype='i8')

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if vc[v1][v2] == -1:
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[v1][v2] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[v1][v2])


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import numpy as np
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    edge = [[] for _ in range(N)]
    ab = [tuple() for _ in range(N - 1)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)
        ab[i] = (a, b)

    # print(ab)
    # print(edge)

    max_v = 0
    max_v_dim = 0
    for i, e in enumerate(edge):
        if max_v_dim < len(e):
            max_v_dim = len(e)
            max_v = i

    # print(max_v)
    # print(max_v_dim)

    # bfs
    q = deque()
    q.append(max_v)
    ec = np.full(N, -1, dtype='i8')
    ec[max_v] = max_v_dim + 10
    vc = dict()
    # vc = np.full((N, N), -1, dtype='i8')

    while q:
        nv = q.popleft()
        nc = ec[nv]
        tc = 1
        for v in edge[nv]:
            v1, v2 = min(nv, v), max(nv, v)
            if not ((v1, v2) in vc):
                if nc == tc:
                    tc += 1
                ec[v] = tc
                vc[(v1, v2)] = tc
                tc += 1
                q.append(v)

    print(max_v_dim)
    for v1, v2 in ab:
        print(vc[(v1, v2)])


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys

input = lambda: sys.stdin.readline().rstrip()


def comb(n, k):

    if n < k:
        return 0

    m = 1
    for i in range(n, n - k, -1):
        m = m * i

    n = 1
    for i in range(1, k + 1):
        n = n * i

    return (m // n)


def solve():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    S = [0 for _ in range(N + 1)]

    for i in range(N):
        S[i + 1] = S[i] + A[i] - 1

    if N < K:
        d = dict()
        for i in range(N + 1):
            k = S[i] % K
            if d[k]:
                d[k] += 1
            else:
                d[k] = 1

        ans = 0
        for k, v in d.items():
            ans += comb(v, 2)

        print(ans)
        exit()

    elif N >= K:

        ans = 0
        d = dict()

        # first
        kf = S[0] % K
        for i in range(K):
            k = S[i] % K
            if k in d:
                d[k] += 1
            else:
                d[k] = 1

        for k, v in d.items():
            ans += comb(v, 2)

        # slide
        for i in range(1, N + 1 - K):
            d[kf] -= 1
            kf = S[i] % K
            k = S[i + K] % K
            if k in d:
                ans += d[k]
                d[k] += 1
            else:
                d[k] = 1

    print(ans)
    exit()


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import bisect
input = lambda: sys.stdin.readline().rstrip()


def solve():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    S = [0 for _ in range(N + 1)]

    for i in range(N):
        S[i + 1] = S[i] + A[i] - 1

    d = dict()
    for i in range(N + 1):
        k = S[i] % K
        if k in d:
            d[k].append(i)
        else:
            d[k] = [i]

    # print(d)

    ans = 0
    for k, v in d.items():
        if len(v) <= 1:
            continue
        else:
            for i in range(len(v)):
                s = v[i] + K - 1
                si = bisect.bisect_right(v, s)
                ans += (si - i) - 1
                # print(i, si)

    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

#define lint long long
#define all(it) it.begin(), it.end()
#define FOR(i, n) for(int i = 0; i < n; i++)
#define FORU(i, a, b, s) for(int i = a; i < b; i += s)
#define FORD(i, a, b, s) for(int i = a; i > b; i -= s)
#define endl "\n"
lint INF = 2e18;
lint MOD = 1e9 + 7;

lint i, j, k, t;

int main() {
    string S;
    lint K;

    cin >> S >> K;

    S += S[0];

    lint cnt = 0;
    regex re(R"(([a-z])\1{0,})");

    for(sregex_iterator it(all(S), re), end; it != end; ++it) {
        auto &&m = *it;
        cnt += m.length() / 2;
    }

    cout << cnt * K << endl;
}

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

# from numba import njit

# input = stdin.readline

def countProcedure(string):
  res = 0
  strCount = 1
  prev = "" # 1つまえの文字
  for i in range(len(string)):
    if string[i] == prev:
      strCount += 1
    else:
      res += strCount // 2
      strCount = 1
    prev = string[i]

  if strCount != 1:
    res += strCount // 2
  return res

def solve(s,k):
  if s[0] != s[-1]:
    return countProcedure(s)*k
  if all(x == s[0] for x in s):
    return len(s)*k//2
  else:
    leftLength = max(i for i in range(1,len(s)) if s[:i]== s[0]*i)
    left = s[0]*leftLength
    right = s[leftLength:]
    ans = countProcedure(left) + countProcedure(right) + countProcedure("".join([right,left]))*(k-1)
    return ans


def main():
  S = input()
  K = int(input())
  # N,M = map(int,input().split())
  # a = list(map(int,input().split()))
  print(solve(S,K))
  
  
if __name__ == '__main__':
  main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

    dp = np.full(2**N, INF, np.int64)
    dp[0] = 0

    for i in range(M):

        next_dp = dp.copy()
        num, a = key[i]

        for j in range(2**N):
            if dp[j] == INF:
                continue
            else:
                next_num = j | num
                next_dp[j] = min(next_dp[j], dp[j])
                next_dp[next_num] = min(next_dp[next_num], dp[j] + a)

        dp = next_dp

    if dp[2**N - 1] == INF:
        ans = -1
    else:
        ans = dp[2**N - 1]

    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

    dp = [INF for _ in range(2**N)]
    dp[0] = 0

    for i in range(M):
        num, a = key[i]
        for j in range(2**N):
            next_num = j | num
            dp[next_num] = min(dp[next_num], dp[j] + a)

    if dp[2**N - 1] == INF:
        ans = -1
    else:
        ans = dp[2**N - 1]

    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = np.array(list(map(int, input().split())), dtype='i8')
    A = A.reshape((1, N))
    B = np.zeros((N, N), dtype='i8')
    for i in range(N):
        B[i][i - N] = 1
        B[i][i + 1 - N] = 1

    ans = np.dot(np.linalg.inv(B), (A * 2).T)
    ans = ' '.join(map(str, list(map(int, ans.flatten().tolist()))))
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = np.array(list(map(int, input().split())), dtype='i8')
    ans = np.zeros(N, dtype='i8')
    A = A * 2
    s = np.sum(A) // 2

    na1 = 0
    for i in range(1, N, 2):
        na1 += A[i]

    ans[0] = s - na1
    for i in range(N - 1):
        ans[i + 1] = A[i] - ans[i]

    print(' '.join(map(str, ans.tolist())))


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = np.array(list(map(int, input().split())), dtype='i8')
    A = A.reshape((1, N))
    B = np.zeros((N, N), dtype='i8')
    for i in range(N):
        B[i][i - N] = 1
        B[i][i + 1 - N] = 1

    ans = np.linalg.inv(B) @ (A * 2).T
    ans = ' '.join(map(str, list(map(int, ans.flatten().tolist()))))
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    A = np.array(list(map(int, input().split())), dtype='i8')
    ans = np.zeros(N, dtype='i8')
    A = A * 2
    s = np.sum(A) // 2

    na1 = 0
    for i in range(1, N, 2):
        na1 += A[i]

    ans[0] = s - na1
    for i in range(N - 1):
        ans[i + 1] = A[i] - ans[i]

    print(' '.join(map(str, ans.tolist())))


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
import math
input = lambda: sys.stdin.readline().rstrip()


def count_div(N, C, D):

    t = N // C + N // D - N // (C * D // math.gcd(C, D))
    return N - t


def solve():

    A, B, C, D = map(int, input().split())
    ans = count_div(B, C, D) - count_div(A - 1, C, D)
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
import fractions
input = lambda: sys.stdin.readline().rstrip()


def count_div(N, C, D):

    t = N // C + N // D - N // (C * D // fractions.gcd(C, D))
    return N - t


def solve():

    A, B, C, D = map(int, input().split())
    ans = count_div(B, C, D) - count_div(A - 1, C, D)
    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys
import itertools
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N = in_n()
    xy = [tuple(in_nn()) for _ in range(N)]

    comb = itertools.combinations(range(N), 2)
    d = defaultdict(int)

    for i, j in comb:
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        xd = x2 - x1
        yd = y2 - y1
        if yd < 0:
            yd = -yd
            xd = -xd
        d[(xd, yd)] += 1

    ans = N - max(d.values())
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
import itertools
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N = in_n()
    xy = [tuple(in_nn()) for _ in range(N)]

    if N == 1:
        print(1)
        exit()

    comb = itertools.combinations(range(N), 2)
    d = defaultdict(int)

    for i, j in comb:
        x1, y1 = xy[i]
        x2, y2 = xy[j]
        xd = x2 - x1
        yd = y2 - y1
        d[(xd, yd)] += 1
        d[(-xd, -yd)] += 1

    ans = N - max(d.values())
    # print(d)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()


def solve():
    H, W = map(int, input().split())
    S = [[] for _ in range(H)]
    light = np.zeros((H, W), dtype='i8')
    for i in range(H):
        S[i] = list(input())

    for h in range(H):
        count = 0
        wr = -1
        for w in range(W):
            if S[h][w] == '.':
                if wr == -1:
                    wr = w
                count += 1
            elif S[h][w] == '#':
                if wr != -1:
                    light[h, wr:w] += count
                    wr = -1
                    count = 0
        else:
            if wr != -1:
                light[h, wr:w + 1] += count
                wr = -1
                count = 0

    for w in range(W):
        count = 0
        hr = -1
        for h in range(H):
            if S[h][w] == '.':
                if hr == -1:
                    hr = h
                count += 1
            elif S[h][w] == '#':
                if hr != -1:
                    light[hr:h, w] += count
                    hr = -1
                    count = 0
        else:
            if hr != -1:
                light[hr:h + 1, w] += count
                hr = -1
                count = 0

    print(np.max(light) - 1)


if __name__ == '__main__':
    solve()


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()


def light_count(light, H, W, h, w, count, wr=-1, hr=-1):

    if wr != -1:
        for i in range(h * W + wr, h * W + w):
            light[i] += count
    elif hr != -1:
        for i in range(hr * W + w, h * W + w, W):
            light[i] += count


def solve():
    H, W = map(int, input().split())
    S = [[] for _ in range(H)]
    light = [0 for _ in range(H * W)]
    for i in range(H):
        S[i] = list(input())

    for h in range(H):
        count = 0
        wr = -1
        for w in range(W):
            if S[h][w] == '.':
                if wr == -1:
                    wr = w
                count += 1
            elif S[h][w] == '#':
                if wr != -1:
                    light_count(light, H, W, h, w, count, wr=wr)
                    wr = -1
                    count = 0
        else:
            if wr != -1:
                light_count(light, H, W, h, w + 1, count, wr=wr)
                wr = -1
                count = 0

    for w in range(W):
        count = 0
        hr = -1
        for h in range(H):
            if S[h][w] == '.':
                if hr == -1:
                    hr = h
                count += 1
            elif S[h][w] == '#':
                if hr != -1:
                    light_count(light, H, W, h, w, count, hr=hr)
                    hr = -1
                    count = 0
        else:
            if hr != -1:
                light_count(light, H, W, h + 1, w, count, hr=hr)
                hr = -1
                count = 0

    print(max(light) - 1)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    S = in_s()
    N = len(S)

    def abc_count():

        count = 0
        fa, fb = False, False
        for i in range(N):
            if S[i] == 'A':
                fa = True
            elif fa and S[i] == 'B':
                fb = True
            elif fb and S[i] == 'C':
                count += 1
                fa, fb = False, False
            else:
                fa, fb = False, False

        return count

    ans = 0
    while True:
        t = abc_count()
        if t == 0:
            break
        else:
            ans += t
            S = S.replace('ABC', 'BCA')

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def t(S):

    N = len(S)

    a = [0] * (N + 1)
    d = [0] * (N + 1)
    for i in range(N):
        if S[i] == 'A':
            a[i + 1] = 1
        else:
            d[i + 1] = 1

    for i in range(N):
        a[i + 1] += a[i]
        d[i + 1] += d[i]

    ans = 0
    for i in range(1, N):
        if S[i] == 'D':
            ans += a[i]

    return ans


def main():

    S = in_s()
    S = S.replace('BC', 'D')
    S = S.replace('B', ' ')
    S = S.replace('C', ' ')

    ans = 0
    for ts in S.split():
        ans += t(ts)

    print(ans)


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

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = map(int, input().split())
    l1, r1 = map(int, input().split())
    card = set(range(l1, r1 + 1))
    for _ in range(M - 1):
        l, r = map(int, input().split())
        card &= set(range(l, r + 1))

    print(len(card))


if __name__ == '__main__':
    solve()


Fixed submission:
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = map(int, input().split())
    card = [0 for _ in range(N + 1)]

    for _ in range(M):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        card[l] += 1
        card[r + 1] -= 1

    for i in range(N):
        card[i + 1] += card[i]

    # print(card)
    print(card.count(M))


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readline_s = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

INF = 10 ** 10 + 7


def main():
    X, Y, Z, K = map(int, readline().split())
    A = sorted(list(map(int, readline().split())), reverse=True)
    B = sorted(list(map(int, readline().split())), reverse=True)
    C = sorted(list(map(int, readline().split())), reverse=True)

    ans = solve1(X, Y, Z, K, A, B, C)
    print('\n'.join(map(str, ans)))


def solve1(X, Y, Z, K, A, B, C):

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])

    AB.sort(reverse=True)
    AB = AB[:min(X * Y, K)]

    ABC = []
    for i in range(len(AB)):
        for j in range(Z):
            ABC.append(AB[i] + C[j])

    ABC.sort(reverse=True)

    return ABC[:K]


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readline_s = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

INF = 10 ** 10 + 7


def main():
    X, Y, Z, K = map(int, readline().split())
    A = sorted(list(map(int, readline().split())), reverse=True)
    B = sorted(list(map(int, readline().split())), reverse=True)
    C = sorted(list(map(int, readline().split())), reverse=True)

    ans = solve1(X, Y, Z, K, A, B, C)
    print('\n'.join(map(str, ans)))


def solve1(X, Y, Z, K, A, B, C):

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])

    AB.sort(reverse=True)
    AB = AB[:min(X * Y, K)]

    ABC = []
    for i in range(len(AB)):
        for j in range(Z):
            ABC.append(AB[i] + C[j])

    ABC.sort(reverse=True)

    return ABC[:K]


if __name__ == '__main__':
    main()