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

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8[:](i8,i8,i8[:])", cache=True)
def solve(N, K, A):
    for _ in range(min(41, K)):
        A_cumsum = np.zeros(shape=N, dtype=np.int64)
        for i in range(N):
            A_cumsum[max(0, i - A[i])] += 1
            b = i + A[i] + 1
            if N - 1 < b:
                pass
            else:
                A_cumsum[b] -= 1
        A = np.cumsum(A_cumsum)
    return A


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    ans = solve(N, K, A)

    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

import numpy as np
from numba import njit

N_ko, K_kai = map(int, input().split())
A_list = list(map(int, input().split()))
A = np.array(A_list, dtype=np.int64)

@njit
def cal_cumsum(A):
    Light_length = np.zeros(N_ko, dtype=np.int64)
    
    for i in range(N_ko):
        left = max(0, i - A[i])
        right = min(N_ko - 1, i + A[i])
        
        Light_length[left] += 1
        
        if (right + 1 < N_ko):
            Light_length[right + 1] -= 1
    
    Light_length = np.cumsum(Light_length)

    return(Light_length)

for k in range(min(42, K_kai)):
    A = cal_cumsum(A)


print(*A)

Solution (Python):
def main():
    N_ko, K_kai = map(int, input().split())
    init_light = list(map(int, input().split()))


    for k in range(min(42,K_kai)):
        light_list = [0 for i in range(N_ko)]

        for i in range(N_ko):
            left = max(0, i - init_light[i])
            right = min(N_ko - 1, i + init_light[i])
            
            light_list[left] += 1

            if (right + 1 < N_ko):
                light_list[right + 1] -= 1
            
        for i in range(1, N_ko):
            light_list[i] += light_list[i - 1]
        
        init_light = light_list

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


if __name__ == '__main__':
    main()

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=0
while True:
    b=[0]*n
    if c==k:
        break
    for i in range(n):
        l=max(i-a[i],0)
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    f=True
    if b[0]!=n:
        f=False
    for i in range(1,n):
        b[i]+=b[i-1]
        if b[i]!=n:
            f=False
    a=b
    c+=1
    if f:
        break
print(*a)

Solution (Python):
from itertools import accumulate
class Imos:
    def __init__(self, n):
        self.A = [0]*(n+1)
        self.n = n

    def __call__(self):
        
        dist = list(accumulate(self.A))[:self.n]
        self.A = [0] * (self.n+1)
        return dist

    def query(self, l, r):
        self.A[l] += 1
        self.A[r] -= 1

n, k, *A = map(int, open(0).read().split())
imos = Imos(n)
for _ in range(min(100, k)):
    for i in range(n):
        imos.query(max(0, i-A[i]), min(i+A[i]+1, n))
    A = imos()
print(*A)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,k = LI()
    a = LI()

    for kk in range(k):
        r = [0] * (n+1)
        for i in range(n):
            c = a[i]
            r[max(0, i - c)] += 1
            r[min(n, i + c + 1)] -= 1

        if r[0] == n and r[n] == -n:
            a = [n] * n
            break

        t = 0
        for i in range(n):
            t += r[i]
            a[i] = t

    return JA(a, " ")


print(main())

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(min(K, 50)):
    B = [0 for k in range(N)]
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if r + 1 < N:
            B[r+1] -= 1
    
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()
   
for b in B:
    print(b, end=" ")

Solution (Python):


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)

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

    for _ in range(min(K,50)):
        B = [0]*N
        for i in range(N):
            l = max(0,i-A[i])
            r = min(N-1,i+A[i])
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1
        for i in range(N-1):
            B[i+1] += B[i]
        A = B

    print(*B)

if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
*A, = map(int, input().split())

b = [i for i in A]
for c in range(K):
    buf = [0]*(N+1)
    for i, j in enumerate(b):
        buf[max(i-j, 0)] += 1
        buf[min(i+j+1, N)] -= 1
    for i in range(1, N+1):
        buf[i] += buf[i-1]
    b = [buf[i] for i in range(N)]
    if all([i==N for i in b]):
        break

print(*b)

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

ans = [0] * (N+1)

for j in range(K):
    ans = [0] * (N+1)
    for i in range(N):
        L = max(0, i-A[i])
        R = min(N, i+A[i]+1)
        ans[L] += 1
        ans[R] -= 1
    for i in range(1, N+1):
        ans[i] += ans[i-1]
    issame = True
    for i in range(N):
        if i != 0:
            if ans[i-1] != N or ans[i-1] != ans[i]:
                issame = False
        A[i] = ans[i]
    if issame:
        break

for i in range(N):
    print(ans[i], end=' ')

Solution (Python):
import numpy as np
from numba import njit

N, K = map(int, input().split())
A = np.array((list(map(int, input().split()))), dtype=np.int64)

@njit
def imos(A):
    B = np.zeros(N, dtype=np.int64)
    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)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * n:

        break
print(" ".join(map(str, a)))

Solution (Python):


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

while K > 0:
    K -= 1
    
    B = [0] * (N + 1)
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1

    C = 0
    for j in range(N):
        C += B[j]
        A[j] = C

    if set(A) == set([N]):
        break

print(*A)

Solution (Python):
import itertools
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
for _ in range(K):
    cumsum = [0] * (N + 2)
    for i, a in enumerate(A):
        i += 1
        cumsum[max(0, i - a)] += 1
        cumsum[min(i + a + 1, N + 1)] -= 1
    A = list(itertools.accumulate(cumsum))[1:N + 1]
    if min(A) == N:
        break
print(' '.join(map(str, A)))

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*(N+1)
C=0
for i in range(K):
  for j in range(N+1):
    B[j]=0
  for j in range(N):
    B[max(0,j-A[j])]+=1
    B[min(N,j+A[j]+1)]-=1
  C=0
  for j in range(N):
    C+=B[j]
    A[j]=C
  if set(A)==set([N]):
    break
print(*A)

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, AS):
    for _i in range(K):
        d = [0] * (N + 1)
        for i in range(N):
            x = AS[i]
            d[max(i - x, 0)] += 1
            d[min(i + x + 1, N)] -= 1
        cur = 0
        ret = [0] * N
        for i in range(N):
            cur += d[i]
            ret[i] = cur
        AS = ret
        if all(x == N for x in ret):
            return ret

    return ret


def main():
    N, K = map(int, input().split())
    AS = list(map(int, input().split()))

    print(*solve(N, K, AS))


T1 = """
5 1
1 0 0 1 0
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    1 2 2 1 2
    """


T2 = """
5 2
1 0 0 1 0
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3 3 4 4 3
    """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
n, K = map(int, input().split())
a = list(map(int, input().split()))
s = [[0]*n for _ in range(100)]
s[0] = a

tmp = [0] * (n+1)
for i in range(K):
    if sum(s[i]) == n**2:
        print(*([n] * n))
        break
    for j in range(n):
        x = s[i][j]
        l, r = max(0, j-x), min(n, j+x+1)
        tmp[l] += 1
        tmp[r] -= 1
    
    for j in range(n):
        tmp[j+1] = tmp[j] + tmp[j+1]
        s[i+1][j] += tmp[j]
    tmp = [0] * (n+1)
else: print(*s[K])

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

def imos(n,a):
  imos_l=[0]*n
  for i in range(n):
    l=max(i-a[i],0)
    r=min(i+a[i],n-1)
    imos_l[l]+=1
    if (r+1)!=n:
      imos_l[r+1]-=1

  b=[0]
  for i in range(1,n+1):
    b.append(imos_l[i-1]+b[i-1])
  return b[1:]

for i in range(k):
  na=imos(n,a)
  if na==a:
    break
  a=na

print(*a)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
L = [0 for _ in range(N+1)]
cnt = 0
while min(A) < N and cnt < K:
    cnt += 1
    for i in range(N):
        L[max(i-A[i], 0)] += 1
        L[min(i+A[i]+1, N)] -= 1
    for i in range(N):
        L[i+1] += L[i]
        A[i] = L[i]
        L[i] = 0
for i in range(N):
    print(A[i], end = ' '*(i!=N-1))

Solution (Python):
from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product









import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        B = list(accumulate(B))
        
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,k=map(int,input().split())
    A=list(map(int,input().split()))

    for i in range(k):
        B=[0]*(n+1)

        for j in range(n):
            val=A[j]
            B[max(0,j-val)]+=1
            B[min(n,j+val+1)]-=1
        
        for k in range(n):
            B[k+1]+=B[k]
        A=B[:-1]

        if A==[n]*(n):
            break
    
    

    print(*A)    
    
resolve()

Solution (Python):
import sys
from itertools import accumulate
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(60 if k >= 60 else k):
        B = [0] * (n + 1)
        for i in range(n):
            left = max(0, i - A[i])
            right = min(n, i + A[i] + 1)
            B[left] += 1
            B[right] -= 1

        B = list(accumulate(B))
        A = B
    print(*B[:n])


if __name__ == '__main__':
    resolve()

Solution (Python):
def aaa(n,k,a):
    for f in range(k):
        a1=[0]*(n+1)
        for x in range(n):
            y=max(0,x-a[x])
            a1[y]=a1[y]+1    
            z=min(n-1,x+a[x])
            a1[z+1]=a1[z+1]-1
        a[0]=a1[0]
        for x in range(1,n):    
            a[x]=a[x-1]+a1[x]
        if a==[n]*n:
            break
    return a

x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]

b=aaa(n,k,a)
for i in range(n):
    print(b[i])

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))

for i in range(min(50, k)):
    DP = [0] * (n+1)
    for j in range(n):
        light = A[j]
        DP[max(0, j-light)] += 1
        DP[min(n, j+light+1)] -= 1

    for j in range(1, n):
        DP[j] += DP[j-1]

    A = DP[:-1]

print(*A)

Solution (Python):

import numpy as np
from numba import njit
n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def imos(n, A):
    B = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        left = max(0, i - A[i])
        right = min(n, i + A[i] + 1)
        B[left] += 1
        B[right] -= 1
    B = np.cumsum(B)
    return B[:-1]

def solve(n,k,A):
    for i in range(k):
        A = imos(n, A)
        min_A = min(A)
        if min_A == n:
            return A
    return A

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

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, k = mi()
    L = lmi()

    for _ in range(k):
        if min(L) == n:
            break
        imos = [0] * n
        for i in range(n):
            num = L[i]
            imos[max(0, i - num)] += 1
            if i + num + 1 <= n - 1:
                imos[i + num + 1] -= 1
        for i in range(1, n):
            imos[i] += imos[i-1]
        L = imos
    
    print(*L, sep=' ')



if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
N,K = map(int,input().split())
A = np.array(input().split(),dtype=int)
I = np.arange(N)
for i in range(K):
  X = np.zeros(N+1,int)
  np.add.at(X,np.maximum(I-A,0),1)
  np.add.at(X,np.minimum(I+A+1,N),-1)
  A = X.cumsum()[:-1]
  if np.all(A==N):
    break
print(*A)

Solution (Python):
import numpy as np
from numba import njit
 
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)
 
@njit
def imos(a):
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
 
for q in range(k):
  a = imos(a)
  if np.min(a)==n:
    break
    
print(*a)

Solution (Python):
import numpy as np
from numba import njit
 
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)
 
@njit
def loop1(a):
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
 
for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)

Solution (Python):
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from copy import copy
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inar():
    return [int(k) for k in input().split()]


def main():
    n,k=map(int,input().split())
    ar=list(map(int,input().split()))
    fr=[0]*(n+1)
    while(k):
        for i in range(n):
            mn=max(0,i-ar[i])
            mx=min(n-1,i+ar[i])
            fr[mn]+=1
            fr[mx+1]-=1
        k-=1
        for i in range(1,n):
            fr[i]=fr[i]+fr[i-1]
        ok=True
        for i in range(n):
            if(ar[i]!=fr[i]):
                ok=False
                break
        if(ok):
            break
        ar=copy(fr)
        fr = [0] * (n + 1)
    for i in range(n):
        print(ar[i],end=' ')
    print()












BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
 
for k in range(K):
  B = [0]*N
  for i in range(N): 
    start = max(0, i-A[i])
    end = min(N, i+A[i]+1)
    B[start] += 1
    if end <= N - 1:
      B[end] -= 1
 
  for i in range(1, N):
    B[i] = B[i-1] + B[i] 
  A = B
  if min(A) == N:
    break
 
print(*A)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
now = inpl()
now.append(0)
for _ in range(k):
    pre = now[::]
    now = [0] * (n+1)
    for j in range(n):
        a = max(0,j-pre[j])
        b = min(n,j+pre[j]+1)
        now[a] += 1
        now[b] -= 1
    x = 0
    mi = INF
    for j in range(n):
        x += now[j]
        mi = min(mi,x)
        now[j] = x
    if mi == n:
        break
print(*now[:n])

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans1=[]
ans2=[]
ans1+=a
ans2+=a
for i in range(min(k,50)):
  now=0
  ans2=[]
  ans2+=ans1
  kans=[0]*n
  for j in range(n):
    if j+ans2[j]+1<=n-1:
      kans[j+ans2[j]+1]-=1
    now+=1+kans[j]
    
    ans1[j]=now
  if ans1==list(range(1,n+1)):
    ans1=[n]*n
    break
  now=0
  kans=[0]*n
  for j in range(1,n+1):
    if n-j-ans2[n-j]>=0:
      kans[n-j-ans2[n-j]-1]-=1
    now+=1+kans[n-j]
    
    ans1[n-j]+=now-1



print(*ans1)

Solution (Python):
import itertools
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(min(k,50)):
  imos=[0]*(n+1)
  for j in range(n):
    imos[max(j-a[j],0)]+=1
    imos[min(j+a[j]+1,n)]-=1
  a=list(itertools.accumulate(imos))
  if a[:n]==[n]*n:
    break
    
print(*a[:n])

Solution (Python):
n, k = map(int, input().split())
lst = list(map(int, input().split()))

if n**(1/2) <= k:
    lst = [n for _ in range(n)]
    print(*lst)
else:
    for _ in range(k):
        ans = 0
        dp = [0] * (n + 1)
        for _ in range(n):  
            mx = max(0,_ - lst[_])
            mn = min(n, _ + lst[_] +1)
            dp[mx] += 1
            dp[mn] -= 1
        
        for _ in range(n):
            ans = ans + dp[_]
            lst[_] = ans

    print(*lst[:n])

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

fin = min(A) == N
for j in range(K):
    if fin:
        break
    T = [0] * (N + 1)
    for i in range(N):
        T[max(i - A[i], 0)] += 1
        T[min(i + A[i] + 1, N)] -= 1
    A[0] = T[0]
    fin = A[0] == N
    for i in range(1, N):
        A[i] = A[i - 1] + T[i]
        if A[i] < N:
            fin = False
print(' '.join(list(map(str, A))))

Solution (Python):
from itertools import accumulate

n, k = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(k):
   b = [0] * n
   for i in range(n):
      b[max(0, i-a[i])] += 1
      tmp = i + a[i] + 1
      if tmp < n:
         b[tmp] -= 1
   a = list(accumulate(b))
   if a == [n] * n:
      break

print(*a)

Solution (Python):
n , k = map(int,input().split())
a = list(map(int,input().split()))
for j in range(k):
    b = [0 for i in range(n)]
    for i in range(n):
        b[max(0,i-a[i])] += 1
        if i+a[i]+1 < n:
            b[i+a[i]+1] -= 1
    for i in range(n-1):
        b[i+1] += b[i]
    if a == b:
        print(*b)
        exit()
    a = b[:]
print(*b)

Solution (Python):
from itertools import accumulate
import sys
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
        print(*An)
        sys.exit()
print(*An)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, accumulate
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,K = mis()
    A = lmis()
    for _ in range(K):
        l = [0]*(N+1)
        for i in range(N):
            a = A[i]
            l[max(0, i-a)] += 1
            l[min(N, i+a+1)] -= 1
        A = list(accumulate(l))[:-1]
        if all(a==N for a in A):
            break
    print(*A)

main()

Solution (Python):

"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(min(K, 42)):
        
        imos_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            imos_list[max(i-d, 0)] += 1
            if i+d+1 <= N-1:
                imos_list[i+d+1] -= 1
            
            
            
        for i in range(1, N):
            imos_list[i] += imos_list[i-1]
        A_list = imos_list[:]
        
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

if __name__ == "__main__":
    main()

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(K):
    B = [0] * N
    for n in range(N):
        l = max(0, n- A[n])
        r = min(N-1, n+A[n])
        B[l] += 1
        if r +1 < N:
            B[r+1] -= 1
    
    for i in range(N-1):
        B[i+1] += B[i]
    
    if sum(A) == N**2:
        break
    else:
        A = B[:]
print(*A)

Solution (Python):
n, k = map(int, input().split())

a = list(map(int, input().split()))

def IMOS(a):
    imos = [0]*n
    for i, ai in enumerate(a):
        imos[max(i-ai, 0)] += 1
        if i+ai+1 < n:
            imos[i+ai+1] -= 1
    for i in range(1, n):
        imos[i] += imos[i-1]
    return imos

for _ in range(k):
    if sum(a) == n*n:
        break
    a = IMOS(a)

print(*a)

Solution (Python):
def main(n,k,a):
  for _ in range(k):
    b=[0]*(n+1)
    x=0
    for i,j in enumerate(a):
      b[max(0,i-j)]+=1
      b[min(n,i+j+1)]-=1
    for i in range(n):
      b[i+1]+=b[i]
      if b[i]==n:
        x+=1
    a=b
    if x==n:
      break
  return a
N,K,*A=map(int,open(0).read().split())
r=main(N,K,A)
print(*r[:-1])

Solution (Python):
def main(n,k,a):
  for _ in range(k):
    b=[0]*(n+1)
    for i,j in enumerate(a):
      b[max(0,i-j)]+=1
      b[min(n,i+j+1)]-=1
    for i in range(n):
      b[i+1]+=b[i]
    if a==b:break
    a=b
  print(*a[:-1])
N,K,*A=map(int,open(0).read().split())
main(N,K,A)

Solution (Python):

import copy
N, k = map(int,input().split())
A = list(map(int,input().split()))
B = [0] * N
A = [0] + A


for j in range(k):
    
    n_light = [0] * (N+1)
    for i in range(N):
        d = A[i+1]
        l = i+1-d
        r = i+1+d
        
        n_light[max(l, 1)] += 1
        if r+1 <= N:
            n_light[r+1] -= 1
        
    
    for i in range(1,N):
        n_light[i+1] += n_light[i]
    n_str = [str(i) for i in n_light]
    if len(set(n_light[1:])) == 1 and j > 2:
        
        break
    
    A = n_light
    
print(' '.join(n_str[1:]))

Solution (Python):

from itertools import accumulate
import numpy as np
from numba import njit

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

@njit
def loop1(a):
  
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
  
  
   
  
   

for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)

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


cnt = 0
while cnt < k:
    imos = [0] * (n + 1)
    for i in range(n):
        imos[max(i - a[i], 0)] += 1
        imos[min(i + a[i] + 1, n)] -= 1

    for i in range(n):
        imos[i + 1] += imos[i]

    a = imos[0:n]
    cnt += 1

    if min(a) == n:
        
        break
print(*a)

Solution (Python):
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,K=nm()
A=nl()

imos_l=[0]*(N+1)

for i in range(K):    
    imos_l=[0]*(N+1)
    for j in range(len(A)): 
        imos_l[max(j-A[j],0)]+=1
        imos_l[min(j+A[j]+1,N)]-=1
    for j in range(len(imos_l)-1):
        imos_l[j+1]=imos_l[j]+imos_l[j+1]
    for j in range(len(A)):
        A[j]=imos_l[j]
    flag=True
    for j in range(len(A)):
        if(A[j]<N):
            flag=False
    if(flag):
        print(*A)
        sys.exit(0)

print(*A)