Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_l = [d_l.count(1)]
    for i in range(2, d_max+1):
        count_l.append(d_l.count(i))
    
    for i in range(1, d_max):
        ans = ans * count_l[i-1] ** count_l[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()

Fixed submission:
import sys
import collections


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_dic = collections.Counter(d_l)
    if count_dic[0] != 1:
        print(0)
        sys.exit()
    
    for i in range(2, d_max+1):
        ans *= count_dic[i-1] ** count_dic[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_l = [d_l.count(1)]
    for i in range(2, d_max+1):
        if count_l[i-2] == 0:
            print(0)
            sys.exit()
        count_l.append(d_l.count(i))
    
    for i in range(1, d_max):
        ans = ans * count_l[i-1] ** count_l[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()

Fixed submission:
import sys
import collections


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_dic = collections.Counter(d_l)
    if count_dic[0] != 1:
        print(0)
        sys.exit()
    
    for i in range(2, d_max+1):
        ans *= count_dic[i-1] ** count_dic[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_l = [d_l.count(1)]
    for i in range(2, d_max+1):
        if count_l[i-2] == 0:
            print(0)
            sys.exit()
        count_l.append(d_l.count(i))
    
    for i in range(1, d_max):
        ans = ans * count_l[i-1] ** count_l[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()

Fixed submission:
import sys
import collections


def solve():
    MOD = 998244353
    N, *d_l = map(int, open(0).read().split())
    ans = 1
    
    if d_l[0] != 0:
        print(0)
        sys.exit()
    
    d_max = max(d_l)
    count_dic = collections.Counter(d_l)
    if count_dic[0] != 1:
        print(0)
        sys.exit()
    
    for i in range(2, d_max+1):
        ans *= count_dic[i-1] ** count_dic[i]
    
    print(ans%MOD)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    s = input()
    ans = 0
    
    for i in range(len(s)+1):
        left = 0
        right = 0
        for j in range(i-1, -1, -1):
            if s[j] == '<':
                left += 1
            else:
                break
        for j in range(i, len(s)):
            if s[j] == '>':
                right += 1
            else:
                break
        ans += max(left, right)
    
    print(ans)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    s_arr = input().replace('><', '> <').split()
    ans = 0
    
    for s in s_arr:
        left = s.count('<')
        right = len(s) - left
        if left < right:
            left -= 1
            ans += left * (left + 1) // 2 + right * (right + 1) // 2
        else:
            right -= 1
            ans += left * (left + 1) // 2 + right * (right + 1) // 2
    
    print(ans)

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    s = input()
    ans = 0
    
    for i in range(len(s)+1):
        left = 0
        right = 0
        for j in range(i-1, -1, -1):
            if s[j] == '<':
                left += 1
            else:
                break
        for j in range(i, len(s)):
            if s[j] == '>':
                right += 1
            else:
                break
        ans += max(left, right)
    
    print(ans)

if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    s_arr = input().replace('><', '> <').split()
    ans = 0
    
    for s in s_arr:
        left = s.count('<')
        right = len(s) - left
        if left < right:
            left -= 1
            ans += left * (left + 1) // 2 + right * (right + 1) // 2
        else:
            right -= 1
            ans += left * (left + 1) // 2 + right * (right + 1) // 2
    
    print(ans)

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


def solve():
    N, K = map(int, input().split())
    a_l = np.array(input().split(), int)
    b_l = np.array(input().split(), int)
    a_l.sort()
    b_l.sort()
    b_l = b_l[::-1]

    sum_a = sum(a_l)
    left, right = -1, 10**12
    while left + 1 < right:
        mid = (left + right) // 2
        if sum_a - sum(np.minimum(a_l, mid//b_l)) <= K:
            right = mid
        else:
            left = mid

    print(right)


if __name__ == '__main__':
    solve()

Fixed submission:
import numpy as np


def solve():
    N, K = map(int, input().split())
    a_l = np.array(input().split(), int)
    b_l = np.array(input().split(), int)
    a_l.sort()
    b_l.sort()
    b_l = b_l[::-1]

    sum_a = a_l.sum()
    left, right = -1, 10**13
    while left + 1 < right:
        mid = (left + right) // 2
        if sum_a - np.minimum(a_l, mid // b_l).sum() <= K:
            right = mid
        else:
            left = mid

    print(right)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
    N, M = map(int, input().split())
    INF = 10 ** 9
    
    dp = [INF] * (2 ** N)
    dp[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        c = list(map(lambda x: int(x) - 1, input().split()))
        open = 0
        for i in range(b):
            open += 1 << c[i]
        for i in range(2 ** N):
            if dp[i] + a <= dp[i | open]:
                dp[i | open] = dp[i] + a
    
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


if __name__ == '__main__':
    solve()


Fixed submission:
# coding: utf-8


def solve():
    N = int(input())
    count = 0
    
    for i in range(1, N+1):
        if i % 2 == 1:
            count += 1
    
    print(count/N)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, K, Q = map(int, input().split())
    point = [K for _ in range(N)]
    
    for _ in range(Q):
        answer = int(input()) - 1
        for i in range(N):
            if answer == i:
                continue
            else:
                point[i] -= 1
    
    for i in range(N):
        if point[i] > 0:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N, K, Q = map(int, input().split())
    point = [K for _ in range(N)]
    
    for _ in range(Q):
        answer = int(input()) - 1
        point[answer] += 1
    
    for i in range(N):
        if point[i] > Q:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
numbers = list(map(int, input().split()))

ans = 0
for i in range(N-1):
  x = 0
  for j in range(i, N-1):
    if numbers[j] >= numbers[j + 1]:
      x += 1
      i += 1
      if j == N - 2:
        if x > ans:
          ans = x
    else:
      if x > ans:
        ans = x
      break
      
print(ans)

Fixed submission:
def resolve():
    n = int(input())
    h = list(map(int, input().split()))
    c = 0
    ans = 0
    for i in range(n - 1):
        if h[i + 1] <= h[i]:
            c += 1
            if c > ans:
                ans = c
        else:
            c = 0
    print(ans)
 
 
if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Runtime Error):
import sys


def solve():
    M, D = input().split()
    ans = 0
    m, d_1, d_2 = int(M), int(D[0]), int(D[1])

    if int(M) < 4 or d_1 < 2 and d_2 < 2:
        print(0)
        sys.exit()

    for i in range(4, m+1):
        for j in range(2, d_1+1):
            for k in range(2, 10):
                if j == d_1 and k > d_2:
                    break
                if i == j * k:
                    ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Fixed submission:
import sys


def solve():
    M, D = input().split()
    ans = 0
    
    if int(D) < 22:
        print(0)
        sys.exit()
    
    m, d_1, d_2 = int(M), int(D[0]), int(D[1])

    if int(M) < 4 or d_1 < 2 and d_2 < 2:
        print(0)
        sys.exit()

    for i in range(4, m+1):
        for j in range(2, d_1+1):
            for k in range(2, 10):
                if j == d_1 and k > d_2:
                    break
                if i == j * k:
                    ans += 1
    print(ans)


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


def solve():
    N, Q = map(int, input().split())
    ab = [[0, 0] for _ in range(N-1)]
    for i in range(N-1):
        ab[i] = list(map(int, input().split()))
    px = [[0, 0] for _ in range(Q)]
    for i in range(Q):
        px[i] = list(map(int, input().split()))

    graph = [[] for _ in range(N+1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    val = [0 for _ in range(N+1)]
    for p, x in px:
        val[p] += x

    que = deque([1])
    parent = [0 for _ in range(N+1)]
    while que:
        i = que.popleft()
        for j in graph[i]:
            if j == parent[i]:
                continue
            parent[j] = i
            que.append(j)
            val[j] += val[i]

    print(*val[1:])


if __name__ == '__main__':
    solve()

Fixed submission:
from collections import deque


def solve():
    N, Q = map(int, input().split())
    ab = [[0, 0] for _ in range(N-1)]
    for i in range(N-1):
        ab[i] = list(map(int, input().split()))
    px = [[0, 0] for _ in range(Q)]
    for i in range(Q):
        px[i] = list(map(int, input().split()))

    graph = [[] for _ in range(N+1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    val = [0 for _ in range(N+1)]
    for p, x in px:
        val[p] += x

    que = deque([1])
    parent = [0 for _ in range(N+1)]
    while que:
        i = que.popleft()
        for j in graph[i]:
            if j == parent[i]:
                continue
            parent[j] = i
            que.append(j)
            val[j] += val[i]

    print(*val[1:])


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    abl = [0] * N
    for i in range(N):
        abl[i] = list(map(int, input().split()))
        abl[i][1] *= -1
    
    ans = 0
    hq = []
    hq_hash = []
    for i in range(1, M+1):
        for j in range(N):
            if abl[j][0] <= i and j not in hq_hash:
                heapq.heappush(hq, abl[j][1])
                hq_hash.append(j)
        if len(hq) > 0:
            ans += -heapq.heappop(hq)
    
    print(ans)

if __name__ == '__main__':
    solve()

Fixed submission:
import sys
import heapq
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    jobs = [[] for _ in range(M)]
    for i in range(N):
        a, b = map(int, input().split())
        if a - 1 < M:
            jobs[a-1].append(-b)
    
    ans = 0
    hq = []
    for i in range(M):
        for job in jobs[i]:
            heapq.heappush(hq, job)
        if len(hq) > 0:
            ans += -heapq.heappop(hq)
    
    print(ans)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    MOD = 10**9+7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i+1][(k*10+j)%13] += dp[i][k]
        else:
            num = int(S[i])
            for j in range(13):
                dp[i+1][(j*10+num)%13] += dp[i][j]
    print(dp[N][5]%MOD)


if __name__ == '__main__':
    solve()

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    MOD = 10 ** 9 + 7
    S = rl().rstrip()
    
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    
    for i in range(N):
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
        else:
            num = int(S[i])
            for j in range(13):
                dp[i + 1][(j * 10 + num) % 13] += dp[i][j] % MOD
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
	N, *A = map(int, open(0).read().split())

	top = [A[0]]
	for i in range(1, N):
		da_min = 10**9
		color = -1
		for j in range(len(top)):
			da = A[i] - top[j]
			if da > 0:
				if da_min > da:
					da_min = da
					color = j
		if color != -1:
			top[color] = A[i]
		else:
			top.append(A[i])

	print(len(top))


if __name__ == '__main__':
	solve()

Fixed submission:
r = int(input())
answer = 3 * r ** 2
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
	N, *A = map(int, open(0).read().split())

	top = [A[0]]
	for i in range(1, N):
		da_min = 10**9
		color = -1
		for j in range(len(top)):
			da = A[i] - top[j]
			if da > 0:
				if da_min > da:
					da_min = da
					color = j
		if color != -1:
			top[color] = A[i]
		else:
			top.append(A[i])

	print(len(top))


if __name__ == '__main__':
	solve()

Fixed submission:
from bisect import bisect_left
from collections import deque


def solve():
	N, *A = map(int, open(0).read().split())

	top = deque([A[0]])
	for a in A[1:]:
		if top[0] >= a:
			top.appendleft(a)
		else:
			index = bisect_left(top, a)
			top[index-1] = a
	
	print(len(top))


if __name__ == '__main__':
	solve()

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
	N, *A = map(int, open(0).read().split())
	
	top = [A[0]]
	for i in range(1, N):
		da_min = 10**9
		color = -1
		for j in range(len(top)):
			da = A[i] - top[j]
			if da > 0:
				if da_min > da:
					da_min = da
					color = j
		if color != -1:
			top[color] = A[i]
		else:
			top.append(A[i])
	
	print(len(top))


if __name__ == '__main__':
	solve()

Fixed submission:
from bisect import bisect_left
from collections import deque


def solve():
	N, *A = map(int, open(0).read().split())

	top = deque([A[0]])
	for a in A[1:]:
		if top[0] >= a:
			top.appendleft(a)
		else:
			index = bisect_left(top, a)
			top[index-1] = a
	
	print(len(top))


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

def solve():
    A, B, C, D = map(int, input().split())
    gcd = (C * D) // math.gcd(C, D)
    ans_sub = A-1 - ((A-1) // C + (A-1) // D - (A+1) // gcd)
    ans = B - (B // C + B // D - B // gcd) - ans_sub
    print(ans)

if __name__ == '__main__':
    solve()

Fixed submission:
import fractions

def solve():
    A, B, C, D = map(int, input().split())
    gcd = (C * D) // fractions.gcd(C, D)
    ans_sub = A-1 - ((A-1) // C + (A-1) // D - (A-1) // gcd)
    ans = B - (B // C + B // D - B // gcd) - ans_sub
    print(ans)

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


def solve():
    N = int(input())
    xy = [[0, 0] for _ in range(N)]
    for i in range(N):
        xy[i][0], xy[i][1] = map(int, input().split())
    
    dxy = defaultdict(int)
    for i in range(N - 1):
        for j in range(i + 1, N):
            dxy[(xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])] += 1
            dxy[(xy[j][0] - xy[i][0], xy[j][1] - xy[i][1])] += 1
    
    zeros = max(dxy.values())
    print(N - zeros)


if __name__ == '__main__':
    solve()


Fixed submission:
from collections import defaultdict


def solve():
    N = int(input())
    if N == 1:
        print(1)
        exit()
    xy = [[0, 0] for _ in range(N)]
    for i in range(N):
        xy[i][0], xy[i][1] = map(int, input().split())
    
    dxy = defaultdict(int)
    for i in range(N - 1):
        for j in range(i + 1, N):
            dxy[(xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])] += 1
            dxy[(xy[j][0] - xy[i][0], xy[j][1] - xy[i][1])] += 1
    
    zeros = max(dxy.values())
    print(N - zeros)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
def solve():
    N, M, *a = map(int, open(0).read().split())
    MOD = 1000000007

    dp = [0 for _ in range(N+1)]
    if 1 not in a:
        dp[1] = 1
        if 2 not in a:
            dp[2] = 2
    elif 2 not in a:
        dp[2] = 1

    for i in range(3, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
        if i in a:
            dp[i] = 0
    print(dp[-1])


if __name__ == '__main__':
    solve()

Fixed submission:
def solve():
    N, M, *a = map(int, open(0).read().split())
    ok = [True for _ in range(N+1)]
    for i in range(M):
        ok[a[i]] = False
    MOD = 1000000007

    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    for i in range(N):
        for j in range(i+1, min(N+1, i+3)):
            if ok[j]:
                dp[j] += dp[i]
                dp[j] %= MOD
    print(dp[N])


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


def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    heapify(A)
    
    for _ in range(M):
        B, C = map(int, input().split())
        for _ in range(B):
            if A[0] < C:
                heappop(A)
                heappush(A, C)
            else:
                break
    
    print(sum(A))


if __name__ == '__main__':
    solve()

Fixed submission:
from operator import itemgetter


def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    BC = [[] for _ in range(M)]
    for i in range(M):
        BC[i] = list(map(int, input().split()))
    BC.sort(key=itemgetter(1), reverse=True)
    
    change = []
    for b, c in BC:
        change += [c for _ in range(b)]
        if N < len(change):
            break
    
    A += change
    A.sort()
    ans = sum(A[-N:])
    print(ans)


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


def solve():
    N, M = map(int, input().split())
    xy_dict = defaultdict(int)
    xy = [[] for _ in range(N)]
    for _ in range(M):
        x, y, z = map(lambda j: int(j)-1, input().split())
        xy_dict[x] += 1
        xy_dict[y] += 1
        xy[x].append(y)
        xy[y].append(x)
    
    xy_sorted = sorted(xy_dict.items(), key=itemgetter(1), reverse=True)
    opened = [0 for _ in range(N)]
    ans = N
    length = len(xy_sorted)
    for i in range(length):
        parent = xy_sorted[i][0]
        if opened[parent] == 1:
            for child in xy[parent]:
                if opened[child] == 0:
                    opened[child] = 1
                    ans -= 1
            continue
        opened[parent] = 1
        for child in xy[parent]:
            opened[child] = 1
        ans -= xy_dict[parent]
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    N, K = map(int, input().split())
    s = input()
    s_lower = s.lower()
    s = list(s)
    s[K-1] = s_lower[K-1]
    print(''.join(s))

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


def solve():
    N, M = map(int, input().split())
    xy_dict = defaultdict(int)
    xy = [[] for _ in range(N)]
    for _ in range(M):
        x, y, z = map(lambda j: int(j)-1, input().split())
        xy_dict[x] += 1
        xy_dict[y] += 1
        xy[x].append(y)
        xy[y].append(x)
    
    xy_sorted = sorted(xy_dict.items(), key=itemgetter(1), reverse=True)
    opened = [0 for _ in range(N)]
    ans = N
    for i in range(M):
        parent = xy_sorted[i][0]
        if opened[parent] == 1:
            for child in xy[parent]:
                if opened[child] == 0:
                    opened[child] = 1
                    ans -= 1
            continue
        opened[parent] = 1
        for child in xy[parent]:
            opened[child] = 1
        ans -= xy_dict[parent]
    print(ans)


if __name__ == '__main__':
    solve()


Fixed submission:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


def solve():
    N, M = map(int, input().split())
    X = [0 for _ in range(M)]
    Y = X[:]
    for i in range(M):
        X[i], Y[i], _ = map(lambda x: int(x)-1, input().split())
    
    graph = csr_matrix(([1]*M, (X, Y)), (N, N))
    ans = connected_components(graph)[0]
    print(ans)


if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from operator import itemgetter


def solve():
    N, M = map(int, input().split())
    xy_dict = defaultdict(int)
    xy = [[] for _ in range(N+1)]
    for _ in range(M):
        x, y, z = map(int, input().split())
        xy_dict[x] += 1
        xy_dict[y] += 1
        xy[x].append(y)
        xy[y].append(x)
    
    xy_sorted = sorted(xy_dict.items(), key=itemgetter(1), reverse=True)
    opened = [0 for _ in range(N+1)]
    ans = N
    for i in range(M):
        parent = xy_sorted[i][0]
        if opened[parent] == 1:
            continue
        opened[parent] = 1
        for child in xy[parent]:
            opened[child] = 1
        ans -= xy_dict[parent]
    print(ans)


if __name__ == '__main__':
    solve()

Fixed submission:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


def solve():
    N, M = map(int, input().split())
    X = [0 for _ in range(M)]
    Y = X[:]
    for i in range(M):
        X[i], Y[i], _ = map(lambda x: int(x)-1, input().split())
    
    graph = csr_matrix(([1]*M, (X, Y)), (N, N))
    ans = connected_components(graph)[0]
    print(ans)


if __name__ == '__main__':
    solve()