Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def solve(N,K,A):
    for i in range(K):
        arr = [0] * (N + 1)

        for ind,j in enumerate(A):
            arr[max(ind-j,0)] += 1
            arr[min(ind+j+1, N)] -= 1

        A[0] = arr[0]
        for k in range(N-1):
            A[k+1] = A[k] + arr[k+1]

        if arr[0] ==N and arr[-1] == -N:
            return A
    return A


if __name__ == "__main__":
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = solve(n,k,a)
    print(*ans)



Fixed submission:
import numpy as np
from numba import njit

@njit('i8,i8,i8[::1]',cache=True)
def solve(N,K,A):
    for i in range(K):
        br = np.zeros(N+1, dtype=np.int64)

        for ind, rux in enumerate(A):
            br[max(ind-rux,0)] += 1
            br[min(ind+rux+1,N)] -= 1
        A = br.cumsum()[:-1]

        if br[0] == N and br[-1] == -N:
            return A
    return A


if __name__ == "__main__":
    n,k = map(int, input().split())
    a = np.array(list(map(int, input().split())),dtype=np.int64)
    ans = solve(n,k,a)
    print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def solve():
    N,K = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(K):
        br = np.zeros(N, dtype=np.int64)
        for ind, rux in enumerate(A):
            br[max(ind-rux,0)] += 1
            l = ind+rux+1
            if l < N:
                br[l] -= 1
        A = br.cumsum()

        #X = br.cumsum()
        #A = X[:-1]ボトルネックっぽい
        if br[0] == N and br[-1] == -N:
            print(*A)
            exit()

    print(*A)

if __name__ == "__main__":
    solve()


Fixed submission:
import numpy as np
from numba import njit

@njit('i8,i8,i8[::1]',cache=True)
def solve(N,K,A):
    for i in range(K):
        br = np.zeros(N+1, dtype=np.int64)

        for ind, rux in enumerate(A):
            br[max(ind-rux,0)] += 1
            br[min(ind+rux+1,N)] -= 1
        A = br.cumsum()[:-1]

        if br[0] == N and br[-1] == -N:
            return A
    return A


if __name__ == "__main__":
    n,k = map(int, input().split())
    a = np.array(list(map(int, input().split())),dtype=np.int64)
    ans = solve(n,k,a)
    print(*ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = np.array(A, dtype=np.int64)

lim = 10**18
if len(B[B==0]) >0:
    print(0)
elif N >59:
    print(-1)
else:
    ans = 1
    for i in A:
        ans *= i
        if ans > lim:
            print(-1)
            exit()
    else:
        if ans >10**18:
            print(-1)
        else:
            print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit()
lim = 10**18

ans = 1
for i in A:
    ans *= i
    if ans > lim:
        print(-1)
        exit()

else:
    if ans >10**18:
        print(-1)
    else:
        print(ans)

Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())),dtype=np.int64)


A = np.array(list(map(int, input().split())),dtype=np.int64)
ans = np.prod(A)
if ans > 10**18:
    print(-1)
elif ans< 0:
    print(-1)
else:
    print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit()
lim = 10**18

ans = 1
for i in A:
    ans *= i
    if ans > lim:
        print(-1)
        exit()

else:
    if ans >10**18:
        print(-1)
    else:
        print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in A:
    ans *= i
if ans >10**18:
  print("-1")
else:
  print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit()
lim = 10**18

ans = 1
for i in A:
    ans *= i
    if ans > lim:
        print(-1)
        exit()

else:
    if ans >10**18:
        print(-1)
    else:
        print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
balls = list(map(int, input().split()))

all = 0
ways =0
for k in range(n):
    delk = balls[0:k] + balls[k + 1::]
    all = 0
    ways= 0
    for i in range(1, n+1):
        a = delk.count(i)
        all += a
        ways += a*(a - 1) // 2
        if all>=n:
            break
    print(ways)


Fixed submission:
n = int(input())
balls = list(map(int, input().split()))
conbi = [0]*n
for i in balls:
    conbi[i-1] +=1
result = 0
for j in range(n):
    result += (conbi[j]*(conbi[j]-1))//2
for k in balls:
    print(result-conbi[k-1]+1, end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
query = [list(map(str, input().split())) for _ in range(q)]

order = True
for i in query:
    if i[0] == "1":
        order = not order
    elif i[1] == "1":
        if order:
            s = i[2] + s
        else:
            s += i[2]
    else:
        if order:
            s += i[2]
        else:
            s = i[2] + s
if not order:
    s = s[::-1]
print(s)

Fixed submission:
from collections import deque
s = deque(input())
q = int(input())
query = [list(map(str, input().split())) for _ in range(q)]

order = True
for i in query:
    if i[0] == "1":
        order = not order
    elif i[1] == "1":
        if order:
            s.appendleft(i[2])
        else:
            s.append(i[2])
    else:
        if order:
            s.append(i[2])
        else:
            s.appendleft(i[2])

if not order:
    s.reverse()
print("".join(s))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())
query = [list(map(str, input().split())) for _ in range(q)]


for i in query:
    if i[0] == "1":
        s =  s[::-1]
    elif i[1] == "1":
        s = i[2] + s
    else:
        s += i[2]

print(s)

Fixed submission:
from collections import deque
s = deque(input())
q = int(input())
query = [list(map(str, input().split())) for _ in range(q)]

order = True
for i in query:
    if i[0] == "1":
        order = not order
    elif i[1] == "1":
        if order:
            s.appendleft(i[2])
        else:
            s.append(i[2])
    else:
        if order:
            s.append(i[2])
        else:
            s.appendleft(i[2])

if not order:
    s.reverse()
print("".join(s))
Buggy python submission (verdict: Runtime Error):
#C - Guess The Number https://atcoder.jp/contests/abc157/tasks/abc157_c
x,m = map(int, input().split())
s=[-1]*m
c=[-1]*m
num = [-1]*3
ans = 0
for i in range(m):
    s[i], c[i] = map(int, input().split())

for j, l in zip(s, c):
    if num[j-1] == -1:
        num[j-1] = l
    elif num[j-1] != l:
        print(-1)
        break

    #num[j-1]とlが同じときは何もされない
else:
    num = list(map(lambda x: x*0 if x<0 else x, num))
    for k in num:
        ans = ans *10 + k
    if ans != 0 and num>1:
        print(ans)
    else:
        print(-1)

Fixed submission:
x,m = map(int, input().split())
s=[-1]*m
c=[-1]*m
for i in range(m):
    s[i], c[i] = map(int, input().split())
if x ==1:
    start = 0
else:
    start = 10**(x-1)

for j in range(start, 1000):
    num = str(j)
    for k1, k2 in zip(s, c):
        if num[k1-1] != str(k2):
            break
    else:  #すべて一致したとき
        print(j)
        break
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    prob = 0
    for i in range(N - K + 1):
        x = 0
        for j in range(K):
            x += 1 + P[i + j]
        prob = max(prob, x / 2)
    print(prob)

if __name__ == '__main__':
    solve()


Fixed submission:
def solve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    x = sum([1+ P[i] for i in range(K)])
    prob = x/2
    for i in range(1,N - K + 1):
        x += P[i+K-1]-P[i-1]
        prob = max(prob, x / 2)
    print(prob)

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
for i in range(1,n+1):
    print(a.index(i)+1,end=" ")
 

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
rev = [0]*(n)
for i in range(n):
    rev[A[i]-1] = i+1
print(" ".join(map(str, rev)))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def solve():
    N,M = map(int, input().split())
    LR = [list(map(int, input().split())) for _ in range(M)]
    data = np.array([0 for _1 in range(N+1)])

    for i in range(M):
        data[LR[i][0]:LR[i][1]+1] += 1
    print(len(data[data==M]))



if __name__ == '__main__':
    solve()


Fixed submission:
import numpy as np
def solve():
    N,M = map(int, input().split())
    LR = np.array([list(map(int, input().split())) for _ in range(M)])
    Lmax = np.max(LR[:,0])
    Rmin = np.min(LR[:,1])
    ans = Rmin - Lmax + 1 if Rmin - Lmax >=0 else 0
    print(ans)





if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
n,q = map(int, input().split())
s = input()
ruiseki = [0]*(n+1)
for j in range(n):
    ruiseki[j+1] = ruiseki[j]
    if s[j] =="A" and s[j+1]=="C":
        ruiseki[j+1] += 1
for i in range(q):
    l, r = map(int, input().split())
    print(ruiseki[r-1] - ruiseki[l-1])




Fixed submission:
n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i:i+2] == "AC":
        ans[i+1] = ans[i]+1
    else:
        ans[i+1] = ans[i]
    #1indexの累積和

for j in range(q):
    l, r = map(int, input().split())
    print(ans[r-1]-ans[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i] = 1
for j in range(q):
    l, r = map(int, input().split())
    print(sum(ans[l - 1:r - 1]))


Fixed submission:
n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i:i+2] == "AC":
        ans[i+1] = ans[i]+1
    else:
        ans[i+1] = ans[i]
    #1indexの累積和

for j in range(q):
    l, r = map(int, input().split())
    print(ans[r-1]-ans[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
l = [0]*q
r = [0]*q
for j in range(q):
    l[j], r[j] = map(int, input().split())

for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        ans[i] = 1
for k in range(q):
    print(sum(ans[l[k] - 1:r[k] - 1]))

Fixed submission:
n, q = map(int, input().split())
s = input()
ans = [0 for _ in range(n)]
for i in range(len(s) - 1):
    if s[i:i+2] == "AC":
        ans[i+1] = ans[i]+1
    else:
        ans[i+1] = ans[i]
    #1indexの累積和

for j in range(q):
    l, r = map(int, input().split())
    print(ans[r-1]-ans[l-1])
Buggy python submission (verdict: Runtime Error):
def routing(x, y, z = 0):
    route = ""
    for i in range(2):
        if z:
            if dy:
                route += "D"
            else:
                route += "U"
        if x:
            route += "R"*(dx+z)
            x = not x
        else:
            route += "L"+(dx+z)
            x = not x
        if y:
            route += "U"*(dy+z)
            y = not y
        elif y:
            route += "D"*(dy+z)
            y = not y
        if z:
            if dx:
                route += "L"
            else:
                route += "R"
    return route

sx, sy, tx, ty = map(int, input().split())
route =""
dx = tx-sx
dy = ty-sy
x = dx>0
y = dy>0
route += routing(dx,dy)
route += routing(dx,dy,1)
print(route)

Fixed submission:
sx, sy, tx, ty = map(int, input().split())
route = ""
dx, dy = tx - sx, ty - sy
path1 = "R" * dx + "U" * dy
path2 = "L" * dx + "D" * dy
dx, dy = dx + 1, dy + 1
path3 = "D" + "R" * dx + "U" * dy + "L"
path4 = "U" + "L" * dx + "D" * dy + "R"
ans =path1 + path2 + path3 + path4
print( ans)

Buggy python submission (verdict: Runtime Error):
def routing(x, y, z = 0):
    route = ""
    for i in range(2):
        if z:
            if dy:
                route += "D"
            else:
                route += "U"
        if x:
            route += "R"*(dx+z)
            x = not x
        else:
            route += "L"+(dx+z)
            x = not x
        if y:
            route *= "U"*(dy+z)
            y = not y
        elif y:
            route *= "D"*(dy+z)
            y = not y
        if z:
            if dx:
                route += "L"
            else:
                route += "R"
    return route

sx, sy, tx, ty = map(int, input().split())
route =""
dx = tx-sx
dy = ty-sy
x = dx>0
y = dy>0
route += routing(dx,dy)
route += routing(dx,dy,1)
print(route)

Fixed submission:
sx, sy, tx, ty = map(int, input().split())
route = ""
dx, dy = tx - sx, ty - sy
path1 = "R" * dx + "U" * dy
path2 = "L" * dx + "D" * dy
dx, dy = dx + 1, dy + 1
path3 = "D" + "R" * dx + "U" * dy + "L"
path4 = "U" + "L" * dx + "D" * dy + "R"
ans =path1 + path2 + path3 + path4
print( ans)
Buggy python submission (verdict: Runtime Error):
l, n = map(int, input().split())
s = [input() for _ in range(n)]
s.sort()
print("".join(s))

Fixed submission:
N, _ = [int(x) for x in input().split()]
S = sorted([input() for _ in range(N)])
print(''.join(S))

Buggy python submission (verdict: Runtime Error):
l, n = map(int, input().split())
s = sorted([input() for _ in range(n)])
print("".join(s))

Fixed submission:
N, _ = [int(x) for x in input().split()]
S = sorted([input() for _ in range(N)])
print(''.join(S))

Buggy python submission (verdict: Runtime Error):
l, n = map(int, input().split())
s = sorted([str(input()) for _ in range(n)])
print("".join(s))

Fixed submission:
N, _ = [int(x) for x in input().split()]
S = sorted([input() for _ in range(N)])
print(''.join(S))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
MOD = 998244353
P = []
for _ in range(K):
    l, r = map(int, input().split())
    for i in range(l, r+1):
        P.append(i)
dp = [0]*(N+1)
dp[0]=1
for i in range(N):
    for p in P:
        dp[min(i+p,N)] += dp[i]
        dp[min(i + p, N)]%=MOD
print(dp[N-1])

Fixed submission:
N, K = map(int, input().split())
MOD = 998244353
D = []
for _ in range(K):
    l, r = map(int, input().split())
    D.append((l,r))
imos = [0]*(N+2)
dp = [0]*(N+1)
imos[0]=1
imos[1]=-1
for i in range(N):
    dp[i] = dp[i-1] + imos[i]
    dp[i] %= MOD
    for a, b in D:
        imos[min(i+a,N+1)] += dp[i]
        imos[min(i+b+1,N+1)] -= dp[i]

print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
H, W, M = map(int, input().split())
A = [0]*H
B = [0]*W
D = set()
for _ in range(M):
    h,w = map(int, input().split())
    A[h-1] += 1
    B[w-1] += 1
    D.add((h-1,w-1))
a, b = max(A), max(B)
res = a+b-1
for i in range(H):
    for j in range(W):
        if (A[i],B[j]) == (a,b):
            if (i,j) not in D:
                print(res+1)
                exit()
print(res)

Fixed submission:
H, W, M = map(int, input().split())
A = [0]*H
B = [0]*W
D = set()
for _ in range(M):
    h,w = map(int, input().split())
    A[h-1] += 1
    B[w-1] += 1
    D.add((h-1,w-1))
a, b = max(A), max(B)
res = a+b-1
E, F = [], []
for i in range(H):
    if A[i] == a:
        E.append(i)
for j in range(W):
    if B[j] == b:
        F.append(j)
for i in E:
    for j in F:
        if (i,j) not in D:
            print(res+1)
            exit()
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
    p = start
    for _ in range(L):
        front.append(p)
        p = lift(p)
    if L != N:
        for _ in range(L,R):
            cycle.append(p)
            p = lift(p)
        for _ in range(N-(N-L)%period,N):
            end.append(p)
            p = lift(p)
        cnt = (N-L)//period
    return front, cycle, end, cnt

################################################################################


import sys
input = sys.stdin.readline
from itertools import accumulate

def lift(x): return P[x-1]

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
res = -float("inf")
for i in range(1,N+1):
    front, cycle, end, cnt = cycle_getter(K,i)
    S = sum(C[j-1] for j in front)
    T = sum(C[j-1] for j in cycle)
    if cycle+end:
        U = max(0, max(accumulate(C[j-1] for j in cycle+end)))
    else: U=0
    if front:
        R = max(accumulate(C[j-1] for j in front))
    else: R=0
    res = max(res, S+T*(cnt-1)+U, S+U, R)
print(res)

Fixed submission:
def max2(x,y):
    return x if x > y else y

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

off = max(C)
m2 = off
for i in range(N):
    tmp = 0
    m1 = off
    l = i
    S = 0
    k = 0
    for j in range(N):
        S += C[l]
        l = P[l] - 1
        if l==i:
            k = j+1
            break
    cnt = K // k - (K % k == 0)
    cnt = max2(0, cnt -2)
    a = K-cnt*k
    l = i
    for j in range(a):
        tmp += C[l]
        m1 = max2(m1, tmp)
        l = P[l] - 1
    if S > 0:
        m1 += cnt*S
    m2 = max2(m1, m2)

print(m2)
"""
2 4
2 1
10 -7
"""
Buggy python submission (verdict: Runtime Error):
class cumsum2D:
    def __init__(self, data):
        self.N = len(data)
        self.M= len(data[0])
        self.cum = [[0] * (self.M + 1) for _ in range(self.N + 1)]
        for i in range(self.N):
            for j in range(self.M):
                self.cum[i + 1][j + 1] = self.cum[i][j + 1] + self.cum[i + 1][j] - self.cum[i][j] + data[i][j]

    def get(self,x1,y1,x2,y2):
        """
        長方形の領域 [x1,x2)*[y1,y2) の範囲内にインプットされた数字の和を取る
        """
        return self.cum[x2][y2] - self.cum[x1][y2] - self.cum[x2][y1] + self.cum[x1][y1]

def five(x):
    cnt1 = 0
    while x%5==0:
        cnt1+= 1
        x = x//5
    cnt2 = 0
    while x%2==0:
        cnt2+= 1
        x = x//2
    return (min(cnt1,18), min(cnt2,18))

def digit_lift(S, l):
    if '.' in S:
        a, b = S.split('.')
        n = int(a + b) * 10 ** (l - len(b))
    else:
        n = int(S) * 10 ** l
    return n

data = [[0]*18 for _ in range(18)]

N = int(input())
Q = set()
for _ in range(N):
    A = digit_lift(input().rstrip(),9)
    x, y = five(A)
    data[x][y] += 1
    Q.add((x,y))

cum = cumsum2D(data)
res = 0
for x, y in Q:
    res += cum.get(18-x,18-y,-1,-1)*data[x][y]
print((res-2*data[9][9])//2)

Fixed submission:
def five(x):
    cnt1 = 0
    while x%5==0:
        cnt1+= 1
        x = x//5
    cnt2 = 0
    while x%2==0:
        cnt2+= 1
        x = x//2
    return (min(cnt1,18), min(cnt2,18))

N = int(input())

F = []
for i in range(N):
    A = float(input())
    A = round(A*(10**9))
    F.append(five(A))

F.sort()
# print(F)
j = 0
temp = 0
dp = [0]*19
k = 0
for i in range(N-1):
    if N-1-j < i:
        dp[min(F[i][1], 18)] -= 1
        # print(i, N - j - 1, dp)
    while N-1-j> i and F[i][0]+F[N-1-j][0] >= 18:
        dp[min(F[N-1-j][1],18)] += 1
        # print(i, N - j - 1, dp)
        j += 1
    k = sum(dp[:18-F[i][1]])
    temp += min(j, N-i-1) - k
    # print(j, N-i-1, k, temp)

print(temp)

"""
5
1
1
1
1
1
"""
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
if K%2 == 0 or K%5 == 0:
    print(-1)
    exit()
temp = 7
for i in range(1,10**6):
    if temp%K == 0:
        print(i)
        exit()
    temp += 7*pow(10,i)%K

print(-1)
exit()

Fixed submission:
K = int(input())
if K%2 == 0 or K%5 == 0:
    print(-1)
    exit()
temp = 7%K
for i in range(1,10**6):
    if temp%K == 0:
        print(i)
        exit()
    temp += 7*pow(10,i,K)

print(-1)
exit()
Buggy python submission (verdict: Time Limit Exceeded):
import math

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

N = int(input())

prime_list = make_prime_list_2(N+1)
print(sum(k*search_divisor_num_1(k) for  k in range(1,N+1)) )

Fixed submission:
N = int(input())
ans = 0
for i in range(1, N+1):
    for j in range(i, N+1, i):
        ans += j
print(ans)