Problem:


Score : 500 points

Problem Statement

We have N bulbs arranged on a number line, numbered 1 to N from left to right.
Bulb i is at coordinate i.

Each bulb has a non-negative integer parameter called intensity.
When there is a bulb of intensity d at coordinate x, the bulb illuminates the segment from coordinate x-d-0.5 to x+d+0.5.
Initially, the intensity of Bulb i is A_i. We will now do the following operation K times in a row:

For each integer i between 1 and N (inclusive), let B_i be the number of bulbs illuminating coordinate i. Then, change the intensity of each bulb i to B_i.

Find the intensity of each bulb after the K operations.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq 2 \times 10^5

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the intensity A{'}_i of each bulb i after the K operations to Standard Output in the following format:

A{'}_1 A{'}_2 \ldots A{'}_N

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

Initially, only Bulb 1 illuminates coordinate 1, so the intensity of Bulb 1 becomes 1 after the operation.
Similarly, the bulbs initially illuminating coordinate 2 are Bulb 1 and 2, so the intensity of Bulb 2 becomes 2.

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 41)):
    b = [0]*(n+1)
    for i in range(n):
        b[max(i-a[i], 0)] +=1
        if i+a[i] <n:
            b[i+a[i]+1] -=1
    for i in range(1,n):
        b[i] += b[i-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 42)):
    b = [0]*(n+1)
    for i in range(n):
        b[max(i-a[i], 0)] +=1
        if i+a[i] <n:
            b[i+a[i]+1] -=1
    for i in range(1,n):
        b[i] += b[i-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def update(a):
    b = [0]*(n+1)
    for i in range(n):
        b[max(i-a[i], 0)] +=1
        if i+a[i] <n:
            b[i+a[i]+1] -=1
    for i in range(1,n):
        b[i] += b[i-1]
    return b[:n]

end = [n]*n

for i in range(min(k, 42)):
    a = update(a)
for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Time Limit Exceeded

Solution code:
import collections

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

for k in range(K):
    b = [0 for _ in range(N + 1)]
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(i + a + 1, N)
        b[l] += 1
        b[r] -= 1
    for i in range(N):
        b[i + 1] += b[i]
    b.pop(-1)
    isSame = True
    for i in range(N):
        if not A[i] == b[i]:
            isSame = False
            break
    if isSame:
        break
    A = b

for n in A:
    print(n)

Submission status: Time Limit Exceeded

Solution code:
import math
n, k = map(int, input().split())
array = list(map(int, input().split()))
Array = [0]*n
def plusone(n):
    return n + 1

for j in range(min(k, int(math.log2(n)))):
    for i in range(n):
        ai = array[i]
        Array[max(i-ai, 0):min(i+ai+1,n+1)] = map(plusone, Array[max(i-ai, 0):min(i+ai+1,n+1)])
        #if j == min(k, int(math.log2(n))):
        answer = Array
    array = Array
    Array = [0] * n

print(' '.join(map(str, answer)))

Submission status: Time Limit Exceeded

Solution code:
import collections

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

for k in range(K):
    b = [0 for _ in range(N + 1)]
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(i + a + 1, N)
        b[l] += 1
        b[r] -= 1
    for i in range(N):
        b[i + 1] += b[i]
    b.pop(-1)
    if collections.Counter(A) == collections.Counter(b):
        break
    A = b

for n in A:
    print(n)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

import numpy as np
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)

    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def strength(A):
  """
  光の強さAのリストを受け取って、操作後の光の強さBのリストを返す
  """
  
  # Aと同じ要素数の配列Bで初期化
  B = [0] * len(A)
  
  # Aの要素数の数だけループを回し、Aの要素の値分、横の要素に値を加える
  for i in range(len(A)):
    
    # 影響する最小/最大座標
    min = i - A[i]
    max = i + A[i]
    
    # 最小から最大まで1加える
    if (min < 0):
      min = 0
    if (max + 1 > N):
      max = N
    else:
      max = max + 1
    for j in range(min, max):
      B[j] += 1
  
  return B

  
# 電球の数N, 操作回数K
N, K = map(int, input().split())

# 最初の光の強さA
A = list(map(int, input().split()))

# 操作をK回実行する
B = []

for k in range(K):
  B = strength(A)
  A = B

print(*B)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int, input().split()))

from itertools import accumulate

for _ in range(k):
    imos=[0]*(n+1)
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n,i+a[i]+1)
        imos[l]+=1
        imos[r]-=1
    a=list(accumulate(imos[:n]))
    if a.count(n)==n:
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
def resolve():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())), np.int64)

    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)

        if np.all(A == N):
            print(*A[:-1])
            return
    else:
        print(*A[:-1])

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def update(a):
    b = [0]*(n+1)
    for i in range(n):
        b[max(i-a[i], 0)] +=1
        if i+a[i] <n:
            b[i+a[i]+1] -=1
    for i in range(1,n):
        b[i] += b[i-1]
    return b[:n]
end = [n]*n

for i in range(k):
    if a == end:
        break
    a = update(a)
for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Time Limit Exceeded

Solution code:

from itertools import accumulate
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(K):
        imos_table = [0] * (N + 1)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a+1, N)] -= 1
        A = list(accumulate(imos_table))[:-1]

        if all([True if a == N else False for a in A]):
            print(*A)
            return
    else:
        print(*A)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    l = []
    b = [0]*n
    for i in range(1, n+1):
        x = i-a[i-1]-0.5
        y = i+a[i-1]+0.5
        l.append([x, y])
    for j in range(1, n+1):
        for x, y in l:
            if x <= j <= y:
                b[j-1] += 1
    a = b
print(' '.join(map(str, b)))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))+[0]
p=50

if K<=p:    
    for i in range(K):
        B=[0]+[0]*N+[0]
        for j in range(1,N+1):
            left  = max(0,j-A[j])
            right = min(N+1,j+A[j]+1)
            B[left]  += 1
            B[right] -= 1
        A[0]=B[0]
        for k in range(1,N+1):
            A[k]=A[k-1]+B[k]
else:
    A=[N]*(N+2)
print(*A[1:N+1])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))+[0]
p=100

if K<=p:    
    for i in range(K):
        B=[0]+[0]*N+[0]
        for j in range(1,N+1):
            left  = max(0,j-A[j])
            right = min(N+1,j+A[j]+1)
            B[left]  += 1
            B[right] -= 1
        A[0]=B[0]
        for k in range(1,N+1):
            A[k]=A[k-1]+B[k]
else:
    A=[N]*(N+2)
print(*A[1:N+1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * N

for _ in range(min(K, 41)):
    for j,num in enumerate(A):
        for k in range(max(j-num, 0), min(j+num, N-1) + 1):
            B[k] += 1
    A, B = B.copy(), [0] * N

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import collections

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

for k in range(K):
    b = [ 0 for _ in range(N + 1)]
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(i + a + 1, N)
        b[l] += 1
        b[r] -= 1
    for i in range(N):
        b[i+1] += b[i]
    b.pop(-1)
    if collections.Counter(A) == collections.Counter(b):
        break
    A = b

print(" ".join([str(num) for num in A]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(k):
    newa = [0 for _ in range(n)]
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n - 1, i + a[i])
        newa[l] += 1
        if r + 1 < n:
            newa[r + 1] -= 1
    a = list(accumulate(newa))
    if all(i == n for i in a):
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if tmp[0] == n and tmp[-1] == -n:
        break
print(*alst)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
alst = list(map(int, input().split()))

for _ in range(k):
    tmp = [0 for _ in range(n + 1)]
    for i, num in enumerate(alst):
        min_ind = max(i - num, 0)
        max_ind = min(i + num + 1, n)
        tmp[min_ind] += 1
        tmp[max_ind] -= 1
    next_num = 0
    for i, num in enumerate(tmp[:-1]):
        next_num += num
        alst[i] = next_num
    if min(alst) == n:
        break
print(*alst)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))

def trans(arr):
    result=[]
    for i in range(1,len(arr)+1):
        ans=0
        for j in range(1,len(arr)+1):
            kyori=abs(i-j)
            if kyori<=arr[j-1]:
                ans+=1
            else:
                continue
        result.append(ans)
    arr=result
    return arr

if N<=K:
    ans=[N]*N
    ans=" ".join(map(str,ans))
    print(ans)
else:
    for i in range(K):
        A=trans(A)
    A=" ".join(map(str,A))
    print(A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,k = map(int,input().split())
l = [int(a) for a in input().split()]
m = [N] * N
l_st = [0] * N
for _ in range(k):
    a = np.array(l_st)
    for i,x in enumerate(l):
        if i <= x and  N-i-1 <= x:
            X = [1] * N
        elif i <= x:
            X = [1] * (i+1+x) + [0] * (N-i-x-1)
        elif N-i-1 <= x:
            X = [0] * (i-x) + [1] * (x+N-i)
        else:
            X = [0] * (i-x) + [1] * (2*x + 1) + [0] * (N-x-i-1)
        a += np.array(X)
    a_l = a.tolist()
    if a_l == m:
        break
    else:
        l = a_l
print(' '.join(map(str, a)))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
Ai = input().split()
Bi = [int(i) for i in Ai]

nn = min(50,K)

for n in range(nn):
    li = [0 for i in range(N)]
    for i,x in enumerate(Bi):
        li[i] += 1
        for l in range(1,x+1):
            if i - l >= 0:
                li[i-l] += 1
            if i + l <= N - 1:
                li[i+l] += 1
    Bi = li
for i in li:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
b = A.copy()
for _ in range(min(k,100)):
    add = [0] * (n+1)
    for i, a in enumerate(b):
        add[max(0,i-a)] += 1
        add[min(n,i+a+1)] -= 1
    cumsum = [0] * (n+1)
    for i in range(n):
        cumsum[i+1] = cumsum[i] + add[i]
    b = cumsum[1:]
    #if b == [n] * n:
    #    break
print(' '.join(list(map(str, cumsum[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


for j in range(min(K,42)):
  ans_arr = [0]*(N+1)
  for i in range(N):
    if i==0:
      ans_arr[0]=+1
      ans_arr[min(i+arr[i]+1,N)]=-1
    elif i==N-1:
      ans_arr[max(i-arr[i],0)]+=1
    else:
      ans_arr[max(i-arr[i],0)]+=1
      ans_arr[min(i+arr[i]+1,N)]-=1
  arr = np.array(ans_arr).cumsum()

if K<43:
  print(*arr[:-1])
else:
  arr = [N]*N
  print(*arr)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,k = map(int,input().split())
l = [int(a) for a in input().split()]
m = [N] * N
for _ in range(k):
    a = np.array([0] * N)
    for i,x in enumerate(l):
        if i <= x and  N-i-1 <= x:
            X = [1] * N
        elif i <= x:
            X = [1] * (i+1+x) + [0] * (N-i-x-1)
        elif N-i-1 <= x:
            X = [0] * (i-x) + [1] * (x+N-i)
        else:
            X = [0] * (i-x) + [1] * (2*x + 1) + [0] * (N-x-i-1)
        a += np.array(X)
    a_l = a.tolist()
    if a_l == m:
        break
    else:
        l = a
print(' '.join(map(str, a)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K= map(int,input().split())
A = list(map(int, input().split()))

akarusa = np.array(A)
position = np.array([i for i in range(N)])

K = min(K,100)

for j in range(K):
    tmptmp_akarusa = np.zeros(N+1, dtype=int)
    tmp_akarusa = np.zeros(N, dtype=int)
    for i in range(N):
        akarusa_min = max(0,position[i]-akarusa[i])
        akarusa_max = min(N,position[i]+akarusa[i]+1)
        tmptmp_akarusa[akarusa_min] = tmptmp_akarusa[akarusa_min] + 1
        tmptmp_akarusa[akarusa_max] = tmptmp_akarusa[akarusa_max] - 1
    
    akarusa = np.cumsum(tmptmp_akarusa)

print(*akarusa[:-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


for j in range(K):
  ans_arr = [0]*(N+1)
  for i in range(N):
    if i==0:
      ans_arr[0]=+1
      ans_arr[min(i+arr[i]+1,N)]=-1
    elif i==N-1:
      ans_arr[max(i-arr[i],0)]+=1
    else:
      ans_arr[max(i-arr[i],0)]+=1
      ans_arr[min(i+arr[i]+1,N)]-=1
  arr = np.array(ans_arr).cumsum()
    

print(*arr[:-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K= map(int,input().split())
A = list(map(int, input().split()))

akarusa = np.array(A)
position = np.array([i for i in range(N)])

for j in range(K):
    tmptmp_akarusa = np.zeros(N+1, dtype=int)
    tmp_akarusa = np.zeros(N, dtype=int)
    for i in range(N):
        akarusa_min = max(0,position[i]-akarusa[i])
        akarusa_max = min(N,position[i]+akarusa[i]+1)
        tmptmp_akarusa[akarusa_min] = tmptmp_akarusa[akarusa_min] + 1
        tmptmp_akarusa[akarusa_max] = tmptmp_akarusa[akarusa_max] - 1
    
    akarusa = np.cumsum(tmptmp_akarusa)

print(*akarusa[:-1])

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
n,k = map(int,input().split())
l = [int(x) for x in input().split()]
for p in range(k):
  l2 = [0 for _ in range(n)]
  for i in range(n):
    x = i + 1
    d = l[i]
    r1 = x - d - 0.5
    r2 = x + d + 0.5
    for j in range(1,n+1):
      if(r1 <= j and j <= r2):
        l2[j-1] += 1
  for o in range(n):
    l[o] = l2[o]
l2=[str(a) for a in l2]
l2=" ".join(l2)
print(l2)

Submission status: Time Limit Exceeded

Solution code:
# ac
import numpy as np
# imos法
def update(a):
    n = len(a)
    # b = np.zeros_like(a)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    b = [0 for _ in range(n)]
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n - 1, i + x)  # lampの上限（右側）
        b[l] += 1              # 以下imos法
        if r + 1 < n:          # r+1はx=nの時（最後のサイクル）r+1=nでindexの指定に失敗するから弾く（indexは0~n-1）
            b[r + 1] -= 1
    b = np.cumsum(b)           # bの要素の累積和（フィボナッチ数列みたいな）（imos法の締め）
    return b

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
b = A.copy()
for _ in range(min(k,100)):
    add = [0] * (n+1)
    for i, a in enumerate(b):
        add[max(0,i-a)] += 1
        add[min(n,i+a+1)] -= 1
    cumsum = [0] * (n+1)
    for i in range(n):
        cumsum[i+1] = cumsum[i] + add[i]
    b = cumsum[1:]
    if b == [n] * n:
        break
print(' '.join(list(map(str, cumsum[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import math

def plus(x):
    return x+1

n,k=map(int,input().split())
A=list(map(int,input().split()))
m=min(50,k)
for j in range(m):
    B=[0]*n
    for i in range(n):
        B=B[0:max(0,i-A[i])]+list(map(plus,B[max(0,i-A[i]):min(n,i+A[i]+1)]))+B[min(n,i+A[i]+1):n]
    A=B.copy()

for i in range(n):
    B[i]=str(B[i])

print(' '.join(B))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
Ai = input().split()
Bi = [int(i) for i in Ai]


for n in range(min(100,K)):
    li = [0 for i in range(N)]
    for i,x in enumerate(Bi):
        li[i] += 1
        for l in range(1,x+1):
            if i - l >= 0:
                li[i-l] += 1
            if i + l <= N - 1:
                li[i+l] += 1
    Bi = li
for i in li:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
tmpA = [1 for i in range(N)]
tmpB = []

for i in range(min(K, 50)):
    tmpA = [1 for i in range(N)]
    tmpB = []
    for j in range(N):
        tmpA[j] += len(tmpB)
        tmpB = list(filter(lambda x:x, map(lambda x:x-1, tmpB)))
        if A[j]:
            tmpB.append(A[j])
    
    tmpB = []
    for j in range(N - 1, -1 ,-1):
        tmpA[j] += len(tmpB)
        tmpB = list(filter(lambda x:x, map(lambda x:x-1, tmpB)))
        if A[j]:
            tmpB.append(A[j])

    A = tmpA

[print(i, end=' ') for i in A]
print()

Submission status: Time Limit Exceeded

Solution code:
# ac
import numpy as np
# imos法
def update(a):
    n = len(a)
    b = np.zeros_like(a)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n - 1, i + x)  # lampの上限（右側）
        b[l] += 1              # 以下imos法
        if r + 1 < n:          # r+1はx=nの時（最後のサイクル）r+1=nでindexの指定に失敗するから弾く（indexは0~n-1）
            b[r + 1] -= 1
    b = np.cumsum(b)           # bの要素の累積和（フィボナッチ数列みたいな）（imos法の締め）
    return b

n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K= map(int,input().split())
A = list(map(int, input().split()))

akarusa = np.array(A)
position = np.array([i for i in range(N)])
#tmptmp_akarusa = np.zeros(N+1, dtype=int)
#tmp_akarusa = np.zeros(N, dtype=int)

for j in range(K):
    tmptmp_akarusa = np.zeros(N+1, dtype=int)
    tmp_akarusa = np.zeros(N, dtype=int)
    for i in range(N):
        akarusa_min = max(0,position[i]-akarusa[i])
        akarusa_max = min(N,position[i]+akarusa[i]+1)
        tmptmp_akarusa[akarusa_min] = tmptmp_akarusa[akarusa_min] + 1
        tmptmp_akarusa[akarusa_max] = tmptmp_akarusa[akarusa_max] - 1

    for i in range(N):
        tmp_akarusa[i] = tmptmp_akarusa[0:i+1].sum()
    akarusa = tmp_akarusa

print(*akarusa)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
b = A.copy()
for _ in range(k):
    add = [0] * (n+1)
    for i, a in enumerate(b):
        add[max(0,i-a)] += 1
        add[min(n,i+a+1)] -= 1
    cumsum = [0] * (n+1)
    for i in range(n):
        cumsum[i+1] = cumsum[i] + add[i]
    b = cumsum[1:]
    if b == [n] * n:
        break
print(' '.join(list(map(str, cumsum[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
b = A.copy()
for _ in range(k):
    add = [0] * (n+1)
    for i, a in enumerate(b):
        add[max(0,i-a)] += 1
        add[min(n,i+a+1)] -= 1
    cumsum = [0] * (n+1)
    for i in range(n):
        cumsum[i+1] = cumsum[i] + add[i]
    if b != cumsum[1:]:
        b = cumsum[1:]
    else:
        break
print(' '.join(list(map(str, cumsum[1:]))))

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import numpy as np

n,k = map(int,input().split())
a = np.array(list(map(int,input().split())))

from numba import jit
@jit('i8[:](i8,i8,i8[:])',cache=True)
def solve(n,k,a):
    for j in range(min(k,50)):
        b = np.zeros(n+1,dtype='int64')
        for i in range(n):
            b[max(0,i-a[i])]+=1
            b[min(n,i+a[i]+1)]+=-1
        for i in range(1,n+1):
            b[i] += b[i-1]
        a = b[:n]
    return a

a = solve(n,k,a)
print(' '.join(map(str,a)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit


@njit('i8[:](i8,i8,i8[:])')
def solve(N, K, A):
    for _ in range(K):
        B = np.zeros(N + 1, dtype=np.int64)
        for i in range(N):
            B[max(0, i - A[i])] += 1
            B[min(N, i + A[i] + 1)] -= 1
        if np.all(B == N):
            return B
        A = np.cumsum(B)[:-1]
    return A


N, K = map(int, input().split())
A = np.array(input().split(), dtype=int)
print(' '.join(map(str, solve(N, K, A))))

Submission status: Time Limit Exceeded

Solution code:
#import math
import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal

#N=int(input())
N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())


num=np.zeros(N+1)

for i in range(K):
    n=np.zeros(N,dtype='int')
    for m in range(N):
        l=max(0,m-A[m])
        r=min(N,m+A[m])

        n[l:r+1]+=1
    #    print(l,r)

    A=n
    if A.min() == N:
        for k in range(N):
            print(N)
        exit()

for i in range(N):
    print(n[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
b = A.copy()
for _ in range(k):
    add = [0] * (n+1)
    for i, a in enumerate(b):
        if i-a <= 0:
            add[0] += 1
        else:
            add[i-a] += 1
        if i+a < n-1:
            add[i+a+1] -= 1
        else:
            add[n] -= 1
    cumsum = [0] * (n+1)
    for i in range(n):
        cumsum[i+1] = cumsum[i] + add[i]
    if b != cumsum[1:]:
        b = cumsum[1:]
    else:
        break
print(' '.join(list(map(str, cumsum[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
b = A.copy()
for _ in range(k):
    add = [0] * (n+1)
    for i, a in enumerate(b):
        if i-a <= 0:
            add[0] += 1
        else:
            add[i-a] += 1
        if i+a < n-1:
            add[i+a+1] -= 1
        else:
            add[n] -= 1
    cumsum = [0] * (n+1)
    for i in range(n):
        cumsum[i+1] = cumsum[i] + add[i]
    if b != cumsum:
        b = cumsum[1:]
    else:
        break
print(' '.join(list(map(str, cumsum[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# print(N, K)
# print(A_list)

def update(input_list):
    result_list = np.zeros_like(input_list)
    for index, a in enumerate(input_list):
        index_from = max(0, index - a)
        index_to = min(N, index + a + 1)
        # print(f'index_from, index_to: {index_from, index_to}')
        result_list[index_from:index_to] = result_list[index_from:index_to] + 1
        # print(f'{index}: result_list: {result_list}')
    return result_list


for _ in range(K):
    A_list = update(A_list)
    if np.all(A_list == N):
        # print('break')
        break
    # print(A_list)
print(' '.join(A_list.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# print(N, K)
# print(A_list)

def update(input_list):
    result_list = np.zeros_like(input_list)
    for index, a in enumerate(input_list):
        index_from = max(0, index - a)
        index_to = min(N, index + a + 1)
        # print(f'index_from, index_to: {index_from, index_to}')
        result_list[index_from:index_to] = result_list[index_from:index_to] + 1
        # print(f'{index}: result_list: {result_list}')
    return result_list


for _ in range(K):
    A_list = update(A_list)
    # print(A_list)
print(' '.join(A_list.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))

for t in range(k):
      ok=True
      b=[0]*n
      for i in range(n):
            left=max(0,i-a[i])
            b[left]+=1
            if i+a[i]+1 <= n-1:
                  right=i+a[i]+1
                  b[right]-=1
      for i in range(1,n):
            b[i]=b[i-1]+b[i]
      for i in range(n):
            if a[i]!=b[i]:
                  ok=False
            a[i]=b[i]
      if ok==True:
            break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int, input().split())
A=list(map(int, input().split()))


for k in range(K):
    L=[0]*(N+1)
    for i in range(N):
        L[max(i-A[i],0)]+=1
        L[min(i+A[i]+1,N)]-=1
        #print(L)
    for i in range(N):
        if(0<i):L[i]+=L[i-1]
    if L.count(N)==N:
        L.pop(-1)
        print(' '.join(map(str,L)))
        exit(0)
    else:
        A=L
        
L.pop(-1) 
print(' '.join(map(str,L)))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=[n for i in range(n)]
for j in range(k):
    d=[0 for i in range(n+1)]
    for i in range(n):
        d[max(i-a[i],0)]+=1
        d[min(i+a[i]+1,n)]-=1
    e=[d[i] for i in range(n)]
    for i in range(n-1):#ちょっと特殊な累積和 普通のものの[1:-1]
        e[i+1]=e[i]+d[i+1]
    #print(d,e,sep='\n')
    #print(e)
    a=e
    if e==c:
        break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
array = list(map(int, input().split()))
Array = [0]*n
def plusone(n):
    return n + 1

for j in range(min(k, 41)):
    for i in range(n):
        ai = array[i]
        Array[max(i-ai, 0):min(i+ai+1,n+1)] = map(plusone, Array[max(i-ai, 0):min(i+ai+1,n+1)])
        if j == k - 1:
            answer = Array
    array = Array
    Array = [0] * n

print(' '.join(map(str, answer)))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))

for t in range(k):
      ok=True
      b=[0]*n
      for i in range(n):
            left=max(0,i-a[i])
            b[left]+=1
            if i+a[i]+1 <= n-1:
                  right=i+a[i]+1
                  b[right]-=1
      for i in range(1,n):
            b[i]=b[i-1]+b[i]
      for i in range(n):
            if a[i]!=b[i]:
                  ok=False
            a[i]=b[i]
      if ok:
            break

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

def imos(A):
    B = np.zeros_like(A)
    for i,x in enumerate(A):
        a = max(0, i-x)
        b= min(i+x, N-1)
        B[a] += 1
        if b+1 <= N-1:
            B[b+1] -= 1
    B = np.cumsum(B)
    return B

for i in range(K):
    if i >= 50:
        break
    A = imos(A)
print(*A)