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:
from itertools import accumulate

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

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if a == [n] * n:
        break
print(*a[:-1])

Submission status: Time Limit Exceeded

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

Bs = [1]*N

for i in range (0, N):
	if As[i] > 0:
		for j in range (max(0, i-As[i]),min(i+As[i]+1, N)):
			Bs[j]+=1
		Bs[i]-=1

Cs = [0]*N

switch = 0

for i in range (0, min(K-1, 42)):
	if switch == 0:
		for j in range (0, N):
			for l in range (max(0, j-Bs[j]),min(j+Bs[j]+1, N)):
				if Cs[l] < N:
					Cs[l]+=1
		Bs = [0]*N
		switch = 1
	else:
		for j in range (0, N):
			for l in range (max(0, j-Cs[j]),min(j+Cs[j]+1, N)):
				if Bs[l] < N:
					Bs[l]+=1
		Cs = [0]*N	
		switch = 0

if switch == 0:
	print(*Bs)
else:
	print(*Cs)

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

for _ in range(K):
    acc = [0] * (N + 1)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N, i + a + 1)
        acc[l] += 1
        acc[r] -= 1
    acc[0] = min(N, acc[0])
    for i in range(N):
        acc[i + 1] = min(N, acc[i] + acc[i + 1])
    A = acc[:-1]
    if all(a == N for a in A):
        break
print(*A)

Submission status: Time Limit Exceeded

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

maximized = [False] * N
allmax = [N] * N

for k in range(K):
    B = [0] * N


    # 全玉maxになったとき
    if A == allmax:
        break
    if all(maximized):
        break

    for i in range(N):
        # 強さはN超にはならない
        if A[i] == N:
            B[i] = A[i]
            maximized[i] = True
        else:
            # 照らせる範囲
            l = max(0, i - A[i])
            r = min(N - 1, i + A[i])

            for j in range(l, r + 1):
                B[j] += 1

                if B[j] == N:
                    maximized[j] = True
    A = B

A = [str(a) for a in A]
print(' '.join(A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int,input().split())

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

for j in range(k):
    if j > 41:
        break

    new_a = np.zeros(n, dtype=int)

    for i, x in enumerate(a):
        new_a[i-x if i-x >= 0 else 0:i+x + 1] += 1
   
    a = new_a

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
B = np.zeros(N, dtype="int")
coordinate = np.arange(1, N+1)

limit_count = np.log10(N)
for j in range(K):
    for i in range(N):
        c = coordinate[i]
        B[i] = (A >= np.abs(coordinate - c)).sum()
    A = B.copy()

    if j > limit_count:
        break


print(" ".join(map(str, A.tolist())))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

for k in range(K):
    D = [0]*N

    for i in range(N):
        D[i] += 1
        if A[i] == 0:
            continue

        left = math.ceil(i - A[i] - 0.5)
        right = math.floor(i + A[i] + 0.5)
        if left < 0: left = 0
        if right > N-1: right = N-1
    
        for j in range(left, right+1):
            if i == j: continue
            D[j] += 1

    A = D


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

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
maxed={}
for m in range(0,k):
    temp=[0]*n
    if len(maxed)==n:
        print(' '.join(map(str,a)))
        exit()
    for i in range(0,n):
        d=a[i]
        if d==n:
            temp[i]=n
            maxed[i]=1
        elif d !=0 :
            for x in range(i-d, i+d+1):
                if x >= 0 and x < n :
                    temp[x]+=1
        else:
            temp[i]+=1
    a=copy.copy(temp)

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

Submission status: Time Limit Exceeded

Solution code:
import copy as cp
n,k = map(int,input().split())
lamps = list(map(int,input().split()))
for j in range(min(k,41)):
    lamp_io = [0]*n
    for i in range(len(lamps)):
        if(i == 0):
            for k in range(1,lamps[i]+1):
                if(i+k <= n-1):
                    lamp_io[k] += 1
                else:
                    break
            lamp_io[i] += 1
        elif(i == n-1):
            for k in range(1,lamps[i]+1):
                if(i-k >= 0):
                    lamp_io[i-k] += 1
                else:
                    break
            lamp_io[i] += 1
        else:
            for k in range(1,lamps[i]+1):
                a = 0
                b = 0
                if(i+k <= n-1):
                    lamp_io[i+k] += 1
                else:
                    a = 1
                if(i-k >= 0):
                    lamp_io[i-k] += 1
                else:
                    b = 1
                if(a == 1 and b == 1):
                    break
            lamp_io[i] += 1
        # print(lamp_io)    
    lamps = cp.copy(lamp_io)
ans = ""
for i in range(len(lamp_io)):
    ans += str(lamp_io[i]) +" "
print(ans.rstrip())

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import numpy as np

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,k=map(int, readline().rstrip().split())
    arr=list(map(int, readline().rstrip().split()))
    for _ in range(k):
        tmp=[0]*n
        for i in range(n):
            x = i - arr[i]
            y = i + arr[i] + 1
            if x<0:
                x=0
            if y<n:
                tmp[y]-=1
            tmp[x]+=1
        sm=tmp[0]
        arr[0]=tmp[0]
        for i in range(1,n):
            arr[i]=arr[i-1]+tmp[i]
            sm+=tmp[i]
        if tmp[0]==n and sm==n:
            break
    print(" ".join(map(str,arr)))
    return

    arr=list(map(int, xxx.rstrip().split()))
    n=len(arr)
    k=4

    sp = k

    for _ in range(1):
        tmp=[0]*n
        for i in range(n):
            x = i - arr[i] - sp
            y = i + arr[i] + 1 + sp
            if x<0:
                x=0
            if y<n:
                tmp[y]-=1
            tmp[x]+=1
        arr[0]=tmp[0]
        print(tmp)
        for i in range(1,n):
            arr[i]=arr[i-1]+tmp[i]
    print(" ".join(map(str,arr)))

    arr=list(map(int, xxx.rstrip().split()))
    n=len(arr)
    k=10


    return


    xxx="2 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0"
    arr=list(map(int, xxx.rstrip().split()))
    n=len(arr)
    k=10

    for _ in range(k):
        tmp=[0]*n
        for i in range(n):
            x = i - arr[i]
            y = i + arr[i] + 1
            if x<0:
                x=0
            if y>n:
                y=n
            for j in range(x,y):
                tmp[j]+=1
        arr=tmp
        print(arr)

    arr=list(map(int, xxx.rstrip().split()))
    n=len(arr)
    print("---")
    tmp=[0]*n
    for i in range(n):
        x = i - arr[i]
        y = i + arr[i] + 1
        if x<0:
            x=0
        if y>n:
            y=n
        for j in range(x,y):
            tmp[j]+=1
    arr=tmp
    print(arr)
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    arr=list(map(int, xxx.rstrip().split()))
    n=len(arr)
    print("---")
    tmp=[0]*n
    for i in range(n):
        x = i - arr[i]
        y = i + arr[i] + 1
        if x<0:
            x=0
        if y<n:
            tmp[y]-=1
        tmp[x]+=1
    arr=list(np.cumsum(tmp))
    print(arr)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

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

def light(As,N):
    A0 = np.array([0] * N)
    for i in range(N):
        lp = As[i]
        lmin = max(0, i - lp)
        lmax = min(N - 1, i + lp)
        A0[lmin:lmax + 1] += 1
    return A0

for i in range(K):
    As = light(As, N)
    if sum(As) == N * N:
        break
print(*As,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, k = map(int, input().split())
a_list = np.array(list(map(int, input().split())))

if k > 41:
  print(*([n] * n))
else:
  for ki in range(k):
    b_list = np.array([0] * n)
    i = 0
    for ai in a_list:
      b_list += np.array([0]*(max(0,i-ai)) + [1]*(n-(max(0,i-ai))-(max(0,n-(i+1+ai)))) + [0]*(max(0,n-(i+1+ai))))
      i += 1
    a_list = b_list

  print(*a_list)

Submission status: Time Limit Exceeded

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

A=[int(i) for i in input().split()]
if K > N:
    output=""
    for i in range(N):
         output+=(str(N)+" ")
    print(output)
else:
    for _ in range(K):
        A_next =[1 for i in range(N)]
        for i in range(N):
            for j in range(A[i]):
                if (i+j+1) < N:
                    A_next[i+j+1]+=1
                if (i-j-1) >= 0:
                    A_next[i-j-1]+=1
        A=A_next
    output=""
    for i in A_next:
        output+=(str(i)+" ")
    print(output)

Submission status: Time Limit Exceeded

Solution code:
N , K = map(int,input().split())
Lum = [a for a in map(int,input().split())]

for i1 in range(min(K,50)):
    B = [0 for i in range(N)]
    for i in range(N):
        for j in range(max(0,i-Lum[i]),min(i+Lum[i]+1,N)):
            B[j]+=1
    Lum = B

Lum = [str(l) for l in Lum]
Lum=" ".join(Lum)
print(Lum)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
import sys
input = sys.stdin.readline

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    for i in range(k):
        imos = [0] * (n+1)
        for i in range(n):
            imos[max(0, i-a[i])] += 1
            imos[min(n, i+a[i]+1)] -= 1
        for i in range(n):
            imos[i+1] += imos[i]
        for i in range(n):
            a = copy(imos)
        if all((a[i]==n for i in range(n))):
            break

    for i in a[:-1]:
        print(i, end = ' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def adjust_light(arr):
    counter = [0] * len(arr)
    
    for idx in range(0, len(arr)):
        min = idx - arr[idx]
        if min < 0:
            min = 0
        max = idx + arr[idx]
        if max >= len(arr):
            max = len(arr)-1
        for position in range(min, max+1):
            counter[position] = counter[position] + 1

    return counter

n, k = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
for idx in range(0, k):
    if sum(1 for x in arr if x == len(arr)) == len(arr):
        break
    arr = adjust_light(arr)
print(*arr)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math
import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))

for k in range(K):
    D = [0]*N

    for i in range(N):
        D[i] += 1
        if A[i] == 0:
            continue

        left = math.ceil(i - A[i] - 0.5)
        right = math.floor(i + A[i] + 0.5)
        if left < 0: left = 0
        if right > N-1: right = N-1
    
        for j in range(left, right+1):
            if i == j: continue
            D[j] += 1

    A = D


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

Submission status: Time Limit Exceeded

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

A = A + [0]
for k in range(K):
    t = [0]*(N+1)
    for i in range(N):
        l = max(i-A[i], 0)
        r = min(i+A[i], N-1)
        t[l] += 1
        t[r+1] -= 1

    S = [0]*N
    S[0] = t[0]
    for i in range(1, N):
        S[i] = S[i-1] + t[i]

    A = S.copy()
    if all(a == N for a in A):
        print(*A)
        exit()
print(*S)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))  # 整数のリスト

    next_A = [0 for _ in range(N)]

    for _ in range(K):
        cnt = 0
        if sum(A) == N**2:
            # print("break")
            break
        for i in range(N):
            for j in range(i-A[i], i+A[i]+1):
                if j >= 0 and j < N:
                    next_A[j] += 1
        A = next_A
        next_A = [0 for _ in range(N)]

    for i in A:
        print(i, end=" ")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

for _ in range(K):
    acc = [0] * (N + 1)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N, i + a + 1)
        acc[l] += 1
        acc[r] -= 1
    acc[0] = min(N, acc[0])
    for i in range(N):
        acc[i + 1] = min(N, acc[i] + acc[i + 1])
    A = acc[:-1]

print(*A)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int, K: int, A: "List[int]"):
    for n in range(44 if K>=44 else K):
        L = [0] * N
        for i in range(N):
            for j in range(A[i]+1):
                if j!=0:
                    if i-j>=0:
                        L[i-j] += 1
                    if i+j<N:
                        L[i+j] += 1
                else:
                    L[i+j] += 1
        if A==L:
            A = L
            break
        if sum(A)==N*N:
            A = L
            break
        A = L
 
    print(' '.join(map(str,A)))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr() + [0])
# logNで終了
for _ in range(min(K, 41)):
    next = np.array([0] * (N+1))
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    A = next.cumsum()

print(*A[:-1])

Submission status: Time Limit Exceeded

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

for i in range(K):
    count = np.array([0] * N)
    for j, a in enumerate(A):
        # print(max(0, j-a),min(j+a+1, N))
        count_slice = count[max(0, j-a):min(j+a+1, N)]
        count_slice += 1
    if i >= 1 and (A == count).all():
        break
    else:
    	A = count
print(*count)

Submission status: Time Limit Exceeded

Solution code:
class Range_BIT:
    def __init__(self, n):
        self.n = n
        self.bit0 = [0]*(n+1)
        self.bit1 = [0]*(n+1)
    
    def _Add(self, k, x, is_bit0=True):
        if is_bit0 == True:
            data = self.bit0
        else:
            data = self.bit1
        while k <= self.n:
            data[k] += x
            k += k & -k
    
    def _Get(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k&-k
        return s
    
    """ 配列の獲得 """
    def Array(self):
        array = [0]*(n+1)
        for i in range(self.n):
            array[i] = self.Get(i+1,i+2)
        return array[:-1]
    
    """ 区間[l:r)に対してxを加算 """
    def Add(self, l, r, x):
        self._Add(l, -x*(l-1), is_bit0=True)
        self._Add(r, x*(r-1), is_bit0=True)
        self._Add(l, x, is_bit0=False)
        self._Add(r, -x, is_bit0=False)
    
    """ 区間[l:r)の総和 """
    def Get(self, l, r):
        Pi = self._Get(self.bit1, r-1)*(r-1) - self._Get(self.bit1, l-1)*(l-1)
        Qi = self._Get(self.bit0, r-1) - self._Get(self.bit0, l-1)
        return Pi+Qi

n,k = map(int,input().split())
A = list(map(int,input().split()))
for j in range(k):
    if j==0:
        rbit = Range_BIT(n)
        for i,a in enumerate(A):
            rbit.Add(max(1,i+1-a), min(i+2+a, n+1), 1)
    else:
        A_ = rbit.Array()
        rbit = Range_BIT(n)
        for i,a in enumerate(A_):
            rbit.Add(max(1,i+1-a), min(i+2+a, n+1), 1)
    if set(rbit.Array())=={n}:
        break
print(*rbit.Array())

Submission status: Time Limit Exceeded

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

for k in range(K):
  llist = []
  B = [0] * N
  for i, a in enumerate(A):
    L = list(range(i-a+1, i+a+2))
    for l in L:
      if 1 <= l <= N:
        B[l-1] += 1
  if B.count(N) == N:
    print(*B)
    exit()
  A = B

print(*A)

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
if K >= 40:
    ans = [N]*N
    print(*ans)
else:
    for i in range(K):
        CA = [0]*N
        for j in range(N):
            CA[max(0,j-A[j]):min(j+A[j]+1,N)] = map(lambda x: x+1,CA[max(0,j-A[j]):min(j+A[j]+1,N)])
        A = [CA[i] for i in range(N)]
    print(*A)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

def cal_B(a_list):
    b_list = np.zeros(N, dtype=int)
    for i in range(N):
        temp = np.zeros(N, dtype=int)
        min_x = max(math.ceil(i - a_list[i] - 0.5), 0)
        max_x = min(math.floor(i + a_list[i] + 0.5), N-1)
        
        temp[min_x : max_x+1] = 1
        b_list += temp
    return b_list

if __name__ == "__main__":
    N, K = map(int, input().split())
    A_list = np.array(list(map(int, input().split())))
    B_list = cal_B(A_list)

    for _ in range(K-1):
        B_list = cal_B(B_list)
        if np.all(B_list == N):
            break

    for i in range(N):
        print(B_list[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
B = np.zeros(N, dtype="int")
coordinate = np.arange(1, N+1)

limit_count = np.log(N)
for j in range(K):
    for i in range(N):
        c = coordinate[i]
        B[i] = (A >= np.abs(coordinate - c)).sum()
    A = B.copy()
    if j > limit_count:
        break


print(" ".join(map(str, A.tolist())))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def LI():
    return list(map(int, input().split()))

n, k = LI()
a = LI()

def mina(i, rep):
    global n
    if rep == 0:
        return 0
    else:
        return min(2**(rep-1)+i, 2**rep-1, 2**(rep-1)+(n-i-1), n)

lb = 1
rep = 0

da = dict()
for i in range(n):
    if a[i] != 0:
        da[i] = a[i] 

while lb <= 2*n and rep < k:
    db = defaultdict(int)
    for i in da:
        for j in range(i+mina(i, rep)+1, min(i+mina(i, rep)+da[i], n-1)+1):
            if mina(j, rep+1) < n:
                db[j] += 1
        for j in range(i-mina(i, rep)-1, max(i-mina(i, rep)-da[i], 0)-1, -1):
            if mina(j, rep+1) < n:
                db[j] += 1
    da = db
    lb *= 2
    rep += 1

for i in range(n):
    a[i] = mina(i, k) + da[i]

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()))
A=np.array(a)
l,r=0,0
for i in range(min(41,k)):
    B=np.zeros(n,dtype=np.int64)
    for x,y in enumerate(list(A)):
        l=max(0,x-y)
        r=min(n-1,x+y)
        B[l:r+1]+=1
    A=B
print(*A,sep=' ')

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, K = getNM()
A = getList()

for i in range(K):
    alta = copy.deepcopy(A)
    flag = True
    for i in range(N):
        cnt = 0
        for j in range(N):
            if abs(i - j) <= alta[j]:
                cnt += 1
        if cnt != N:
            flag = False
        A[i] = cnt
    if flag:
        break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
tmp = [N for _ in range(N)]
for _ in range(K):
    answer = [0 for _ in range(N)]
    for i in range(N):
        minus_area = (i + 1) - A[i] - 0.5
        plus_area = (i + 1) + A[i] + 0.5
        if minus_area < 0.5:
            minus_area = 0.5
        if plus_area > N + 0.5:
            plus_area = N + 0.5
        minus_area += 0.5
        plus_area -= 0.5
        for index in range(int(minus_area) - 1, int(plus_area)):
            answer[index] += 1
    if answer == tmp:
        break
    A = answer
 
for a in answer:
    print(a, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import copy
import math
def main():
    N, K = map(int, input().split())
    a = [float(i) for i in input().split()]
    A = [0] * (N + 1)
    if K >= 41:
        for i in range(1, N+1):
            if i > 1:
                print(' ', end='')
            print(N, end='')
        print()
        sys.exit()
    for i in range(1, N+1):
        A[i] = a[i - 1]
    for _ in range(K):
        count = [0] * (N + 1)
        for i in range(1, N+1):
            if A[i] >= N:
                left_d = 1
                right_d = N
            else:
                left_d = math.ceil(i - A[i] - 0.5)
                right_d =  math.floor(i + A[i] + 0.5)
                if left_d < 1:
                    left_d = 1
                if right_d > N:
                    right_d = N
            for j in range(left_d, right_d+1):
                count[j] += 1
        A = copy.copy(count)

    for i in range(1, N+1):
        if i > 1:
            print(' ', end='')
        print(A[i], end='')
    print()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(K):
  newLightPow = [0]*N
  for t_pos in range(1, N+1):
    count = 0
    for pos in range(1, N+1):
      low = float(pos)-(lightPow[pos-1]+0.5)
      high = float(pos)+(lightPow[pos-1]+0.5)
      #print(t_pos)
      #print("low"+str(low)+" high"+str(high))
      if ((low<=t_pos) and (t_pos<=high)):
        #print("yes")
        count += 1
    newLightPow[t_pos-1] = count
  lightPow = newLightPow
print(*lightPow)

Submission status: Time Limit Exceeded

Solution code:
import sys

rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n, k = rm()
a = rl()
k = min(k, 40)
if n <= k:
    for _ in range(n):
        print(n, end=' ')
    exit()
for _ in range(k):
    li = [0] * n
    for i in range(n):
      s = max(i - a[i], 0)
      e = min(i + a[i], n-1)
      for m in range(s, e+1):
        li[m] += 1
    if a == li:
      break
    a = li
for v in a:
    print(v, end=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[3]:


import numpy as np


# In[57]:


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


# In[58]:


light = A
for k in range(K):
    mylist = []
    for n in range(N):
        tmp = [0]*N
        tmp[max(0,n-light[n]):min(N, n+light[n])+1] = [1]*((min(N-1, n+light[n])+1-max(0,n-light[n])))
        mylist.append(tmp)
    light = np.sum(np.array(mylist), axis=0)
print(*light)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
  b=[1]*n
  for i in range(n):
    d=a[i]
    for j in range(max(0,i-d),min(i+d,n-1)+1):
      if i!=j:
        b[j]+=1
  a=copy.deepcopy(b)
ans=""
for i in range(n):
  ans+=str(a[i])
  if i!=n:
    ans+=" "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=list(map(int,input().split(' ')))
A=list(map(int,input().split(' ')))
A2=A
S=[]
if K>=N//5+5:
    l=list(map(str,[N]*N))
    print(" ".join(l))
    exit()
for i in range(K):
    A=A2
    A2=[0]*N
    for i in range(len(A)):
        d=A[i]
        for j in range(d+1):
            if i-j>=0 and j>0:
                A2[i-j]=A2[i-j]+1
            if i+j<N:
                A2[i+j]=A2[i+j]+1
    if [N]*N==A2:
        G=list(map(str,[N]*N))
        print(" ".join(G))
        exit()

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        m = True
        a = [0] * N
        t = 0
        for i in range(N):
            t += a[i] + 1
            if i + A[i] + 1< N:
                a[i + A[i] + 1] -= 1
            a[i] = t
        t = 0
        b = [0] * N
        for i in reversed(range(N)):
            t += b[i]
            b[i] = t
            t += 1
            if i - A[i] - 1 >= 0:
                b[i - A[i] - 1] -= 1
            A[i] = a[i] + b[i]
            if a[i] < N:
                m = False
        if m:
            break
    return A

print(*main())

Submission status: Time Limit Exceeded

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

def imo(a):
    imos=[0]*(n+1)

    for i in range(n):
        imos[max(0,i-a[i])]+=1
        imos[min(n,i+a[i]+1)]-=1
    
    arr=np.array(imos)
    cums=np.cumsum(arr)

    return cums[:n].tolist()

for i in range(min(k,35)):
    a=imo(a)
    
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
last = [n]*n
for i in range(k):
    temp = [0]*n
    min_a = 10**10
    for j in range(n):
        b = a[j]
        min_a = min(b, min_a)
        temp[j] += 1
        for k in range(1, b + 1):
            if j + k < n:
                temp[j + k] += 1
            if j - k >= 0:
                temp[j - k] += 1
    a = temp[:]
    if min_a == n:
        print(*a)
        sys.exit()
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
B = np.zeros(N, dtype="int")
coordinate = np.arange(1, N+1)

limit_count = 0
limit = np.log(N)
for _ in range(K):
    for i in range(N):
        c = coordinate[i]
        B[i] = (A >= np.abs(coordinate - c)).sum()
    A = B.copy()
    if limit_count > limit_count:
        break


print(" ".join(map(str, A.tolist())))

Submission status: Time Limit Exceeded

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
if K >= N:
    ans = [N]*N
    print(*ans)
else:
    for i in range(K):
        CA = [0]*N
        for j in range(N):
            CA[max(0,j-A[j]):min(j+A[j]+1,N)] = map(lambda x: x+1,CA[max(0,j-A[j]):min(j+A[j]+1,N)])
        A = [CA[i] for i in range(N)]
        setA = set(A)
        if setA == N:
            break
    print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,left,right):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            left = i - A[i]
            right = i + A[i] + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B
    return A


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

    res = loop(N,K,A,0,0)

    print(*res)



main()