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: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(K,20)):
    l=[0]*(N+1)
    c=0
    for j in range(N):
        if j-A[j]>0:
            l[j-A[j]]+=1
        else:
            c+=1
        if A[j]+j<N:
            l[A[j]+j+1]-=1 
    for j in range(N):
        c+=l[j]
        A[j]=c
print(*A)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [0] * N
C = [0] * N
for i in range(K):
  B = [0] * N
  C = [0] * N
  p = 0
  q = 0
  for j in range(N):
    x = (j - A[j] - 0.5) // 1 + 1
    y = (j + A[j] + 0.5) // 1 
    if x < 0:
      x = 0
    if y > N - 1:
      y = N - 1
    B[int(x)] = B[int(x)] + 1
    C[int(y)] = C[int(y)] + 1
  for j in range(N):
    if j == 0:
      p = p + B[j]
      A[j] = p
    else:
      p = p + B[j]
      q = q + C[j - 1]
      A[j] = p - q
print(A)

Submission status: Wrong Answer

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

t = 0
while t < k:
  tmpds = [0] * n
  i = 0
  while i < n:
    j = i - ds[i]
    while j <= i + ds[i]:
      if j < 0:
        j += 1
        continue
      if j >= n:
        break
      tmpds[j] += 1
      j += 1
    i += 1
  ds = tmpds.copy()
  t += 1

print(ds)

Submission status: Wrong Answer

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

for kk in range(k):
  hikari = [0]*n
  for i in range(n):
    for j in range(i+1-a[i],i+1+a[i]+1):
      if 0 < j and j < n+1:
        hikari[j-1] += 1
  a = hikari

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

Submission status: Wrong Answer

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

for i in range(K):
    Next = A.copy()
    for i in range(len(A)):
        cnt = 0
        for j in range(len(A)):
            if abs(i-j) <= A[j]:
                cnt+=1
        Next[i] = cnt
    A = Next.copy()
print(Next)

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    key = 1
    nn = n
    while nn > 0:
        key += 1
        nn //= 2
    
    for _ in range(min([key, k])):
        b = [0]*n
        for i in range(n):
            l, r = max([i-a[i], 0]), min([i+a[i], n-1])
            b[l] += 1
            if r != n-1:
                b[r+1] -= 1
        for i in range(n):
            a[i] = 0
            a[i] += b[i]
            if i != 0:
                 a[i] += a[i-1]
    
    print(*a)
            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

for i in range(K):
  B = [0 for j in range(N)]
  for j in range(N):
    s = A[j]
    # i - A[i] ~ i + A[i]
    for k in range(max(0, j - s), min(j+s+1, N)):
      B[k] += 1
  A = [ B[j] for j in range(N)]
  for j in range(N):
    if A[j] < N:
      break
  else:
    break
print(A)

Submission status: Wrong Answer

Solution code:
def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for _ in range(operations):
        dists_new = [0] * number
        for i, d in enumerate(dists):
            start = max(0, i - d)
            end = min(i + d, number - 1)
            for j in range(start, end + 1):
                dists_new[j] += 1
        dists = dists_new[0:]
        if len(set(dists)) == 1:
            break

    print(*dists)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
for k in range(K):
    B = [0 for i in A]
    for i in range(N):
        C = []
        for d in range(A[i]+1):
            if i+d <= N-1:
                C.append(i + d)
            if i-d >= 0:
                C.append(i - d)
        C = list(set(C))
        for c in C:
            B[c] += 1
    A = [b for b in B]
print(B)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if(sum(a)==0):
    print(' '.join(map(str,a)))
    exit()

def update(a):
    b = [0]*n
    for ind,i in enumerate(a):
        left = max(0,ind-i)
        right = ind+i+1
        b[left] += 1
        if(right<n):
            b[right] -= 1

    for i in range(1,n):
        b[i] += b[i-1]

    return b

for i in range(k):
    a = update(a)
    if(sum(a) == n*n):
        break

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

Submission status: Wrong Answer

Solution code:
import numpy as np
# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = [int(v) for v in input().split(" ")]
step = np.arange(len(A_arr))
def Luminate(A_arr, i):
  isLuminated = abs(step - i) < np.array(A_arr)+1
  return isLuminated
def get_Intensity(A_arr):
  return [np.sum(Luminate(A_arr, i)) for i in range(len(A_arr))]
Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity)
print(Intensity)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
import copy
temp=[0]*n
tu=0
td=0
for j in range(k):
  for i in range(n):
    td=max(i+1-a[i],1)
    tu=min(i+1+a[i],n)
    for m in range(td-1,tu):
      temp[m]=temp[m]+1
  a=copy.copy(temp)
L=[str(t) for t in a]
L=" ".join(L)
print(L)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K):
    d=[0]*(N+1)
    for j,a in enumerate(A):
        d[max(0,j-a)]+=1
        d[min(N,j+a+1)]-=1
    b=-1
    for j in range(N):
        if b==-1:
            if d[j]==1 or d[j]==N:
                b=d[j]
            else:
                b=0
        elif b!=d[j]:
            b=0
        d[j+1]+=d[j]
    A=d[:-1]
    if b>0:
        break
print(*A)

Submission status: Wrong Answer

Solution code:
import copy
import sys

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

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

for k in range(K):
    cl=[0]*N
    for i,d in enumerate(a_list):
        start=i-d
        end=i+d
        if start <0:
            start=0
        if end > N-1:
            end=N-1
        
        for k in range(start,end+1):
            cl[k]+=1
        
    if min(cl) == N:
        print(cl)
        sys.exit(0)

    a_list=cl

print(a_list)

Submission status: Wrong Answer

Solution code:
n,k,*a=map(int,open(0).read().split())
import numpy as np
a=np.array(a)
for _ in range(k):
    b=np.zeros(n,int)
    for i in range(n):
        b[max(0,i-a[i]):min(n-1,i+a[i])+1]+=1
    a=b.copy()
print(a)

Submission status: Wrong Answer

Solution code:
#import math
#=input()
#=int(input())
n,k=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

for i in range(k):
    b = [1 for _ in range(n)]
    for j in range(n):
        w = a[j]
        if w != 0:
            for m in range(max(0,j-w),min(n,j+w+1)):
                b[m] += 1
            b[j] -= 1
    if a == b:
        break
    else:
        a = b
print(b)

Submission status: Wrong Answer

Solution code:



n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


for _ in range(k):

    b = [0] * n
    for x in range(n):

        for j in range(0,a[x]+1):

           if  x + j < n:
               b[x+j] += 1
        
        for j in range(1,a[x]+1):

            if x - j >= 0:
                b[x-j] += 1

    for i in range(n):
        a[i] = b[i]


print(a)

Submission status: Wrong Answer

Solution code:
n,k,*a = map(int,open(0).read().split())
for _ in range(k):
  b = [0]*n
  for i in range(n):
    for j in range(max(0,i-a[i]),min(n,i+a[i]+1)):
      b[j]+=1
  a = b
  if b[0] == n and b[-1] == n:
    break
print(b)

Submission status: Wrong Answer

Solution code:
import copy

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


for i in range(k):
    tmp=[]
    for i in range(len(a)):
        tmp.append(1)
    for num, i in enumerate(a):
        for j in range(i):
            j+=1
            if  num+j<len(a):
                tmp[num+j]+=1
            if 0<=num-j:
                tmp[num-j]+=1
    a=tmp

print(a)

Submission status: Wrong Answer

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

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

    a = l[:]

print(a)

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
import copy
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	if K >= 20:
		ans = [N] * N
		print(*ans)
		return

	for i in range(K):
		imos = [0] * (N + 1)
		for j in range(N):
			left = max(0, j - A[j])
			right = min(N, j + A[j] + 1)
			imos[left] += 1
			imos[right] -= 1

		for j in range(N):
			imos[j + 1] += imos[j]

		A = copy.deepcopy(imos[:-1])

	print(*A)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N, K = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]

S = A
D = [0] * len(S)
for _ in range(K):
  for x in range(N):
    D[x] = 0
  for x in range(N):
    D[max(0, x - S[x])] += 1
    if(x + S[x] + 1 < N):
      D[x + S[x] + 1] -= 1
  S[0] = D[0]
  for x in range(1, N):
    S[x] = S[x-1] + D[x]
      
print(S)

Submission status: Wrong Answer

Solution code:
import copy

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

#作業用の配列
b = [0] * n

#k回操作を繰り返す
for i in range(k):
  
  #N個の電球に対し順に操作する
  for j in range(n):
    
    print(a)
    #明るさの初期化
    d = 0
    
    #座標jを照らしている電球の個数を求める
    for l in range(n):
      
      if l - a[l] - 0.5 <= j and j <= l + a[l] + 0.5:
        d += 1
 
    #電球の明るさを更新
    b[j] = d

  a = copy.deepcopy(b)
    
print(' '.join(list(map(str, a))))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
print(a[0])
b = []

for k in range(K):
    b = [0 for _ in range(N)]
    for i in range(N):
        if i - a[i] >= 0:
            start = i - a[i]
        else:
            start = 0
        if i+a[i] < N:
            end = i + a[i] + 1
        else:
            end = N
        for j in range(start, end):
            b[j] += 1
        
    a = b
print(a)

Submission status: Wrong Answer

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

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

def makea(a):
    newa = {}
    for i in range(n):
        newa[i] = 0
    for i in range(n):
        if i - a[i] >= 0:
            if i + a[i] <= n-1:
                for j in range(i-a[i], i+a[i]+1):
                    newa[j] += 1
            else:
                for j in range(i-a[i], n):
                    newa[j] += 1
        elif i + a[i] <= n-1:
            for j in range(i+a[i]+1):
                newa[j] += 1
        else:
            for j in range(n):
                newa[j] += 1
    ans = list(newa.values())
    return ans

for _ in range(k):
    a = makea(a)

print(a)

Submission status: Wrong Answer

Solution code:
l1= input().split(' ')
n= l1[0]
k= int(l1[1])

start= input().split(' ')

def f(ar):
	new= []
	for _ in range(len(ar)):
		new.append(0)
	for index in range(len(ar)):
		d= int(start[index])
		if index-d<0:
			if index+d>len(ar)-1:
				for k in range(0, len(ar)):
					new[k]+=1
			else:
				for k in range(0, index+d+1):
					new[k]+=1
		elif index+d>len(ar)-1:
			for k in range(index-d, len(ar)):
				new[k]+=1
		else:
			for k in range(index-d, index+d+1):
				new[k]+=1
	return new


for _ in range(0,k):
	start= f(start)
print(start)

Submission status: Wrong Answer

Solution code:
import numpy as np


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

loop_cnt = 0
while loop_cnt < k:
    if all(a >= n - 1):
        break

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

    for j in range(n):
        new_a[max(0, j - a[j]): min(n, j + a[j] + 1)] += 1

    a = new_a
    loop_cnt += 1

a += k - loop_cnt

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from itertools import repeat
def main():
    n, k = map(int, stdin.readline().split())
    a = map(int, stdin.readline().split(), repeat(10, n))
    for i in xrange(42):
        b = [0] * (n + 1)
        for j, x in enumerate(a):
            l = j - x
            if l < 0:
                l = 0
            r = j + x + 1
            if r > n:
                r = n
            b[l] += 1
            b[r] -= 1
        s = 0
        for j in xrange(n):
            s += b[j]
            a[j] = s
    stdout.write(' '.join(map(str, a)))
    stdout.write('\n')
main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
now = list(mapint())
if sum(now)==0:
    print(*now)
else:
    for k in range(K):
        nx = [0]*N
        for i, a in enumerate(now):
            for m in range(max(0, i-a), min(i+a+1, N)):
                nx[m] += 1
        now = nx[:]
        if sum(now)==N**2:
            break
    print(*now)

Submission status: Wrong Answer

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

while min(a) < n and k > 0:
  mark = [0] * (n + 1)
  for i in range(n):
    mark[max([0, i - a[i]])] += 1
    mark[min([n, i + a[i] + 1])] -= 1
  a = [mark[0]]
  for i in range(1, n):
    a.append(a[-1] + mark[i])
  k -= 1

a = [a[i] + n * k for i in range(n)]
print(' '.join(map(str, a)))

Submission status: Wrong Answer

Solution code:
import copy

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

for p in range(k):
    B = [0]*n
    for i in range(n):
        if A[i] > 0:
            B[i] += 1
            for j in range(1, A[i]+1):
                if i-j >= 0:
                    B[i-j] += 1
                if i+j < n:
                    B[i+j] += 1

    A = copy.copy(B)

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

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K):
    d=[0]*(N+1)
    for j,a in enumerate(A):
        d[max(0,j-a)]+=1
        d[min(N,j+a+1)]-=1
    b=-1
    for j in range(N):
        if b==-1:
            b=d[j]
        elif b!=d[j] or 1<b<N:
            b=0
        d[j+1]+=d[j]
    A=d[:-1]
    if b:
        break
print(*A)

Submission status: Wrong Answer

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

Anew = [0] * N

for iterate in range(K):
    for i, Ai in enumerate(A):
        for j in range(2 * Ai + 1):
            Anewi = i - Ai + j
            if Anewi < 0 or Anewi >= N:
                continue
            Anew[Anewi] += 1
    A = Anew
    Anew = [0] * N
print(A)

Submission status: Wrong Answer

Solution code:
import numpy as np
Debug = False
# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = [int(v) for v in input().split(" ")]
def Luminate(A_arr, i):
  step = np.arange(len(A_arr))
  distance = abs(step - i)
  isLuminated = distance < np.array(A_arr)+1
  if Debug:
    print(step, distance,isLuminated)
  return isLuminated
def get_Intensity(A_arr):
  return [np.sum(Luminate(A_arr, i)) for i in range(len(A_arr))]
Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity)
print(Intensity)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd, floor
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np

N, K = MAP()
A = LIST()

cnt = 0
while min(A) < N:
	a = [0]*(N+1)
	for i in range(N):
		a[max(0, i-A[i])] += 1
		a[min(N, i+A[i]+1)] -= 1
	A = list(accumulate(a))
	cnt += 1
	if cnt == K:
		print(*A[:-1])
		exit()

A = [x+N*(K-cnt) for x in A]
print(*A[:-1])

Submission status: Wrong Answer

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

for i in range(k):
    b = [None] * n;

    for p in range(n):
        xx = 1;
        
        for q in range(p):
            if p - q <= a[q]:
                xx = xx + 1;
        
        for r in range(p+1,n):
            if r - p <= a[r]:
                xx = xx + 1;
        
        b[p] = xx;
        
    for v in range(n):
        a[v] = b[v];

print(a);

Submission status: Wrong Answer

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

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

if k >= 19:
    print(*([n] * n))
else:
    for ii in range(k):
        B = [0] * (n+1)
        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,len(B)):
            B[i] += B[i-1]
        A = B[:n]
    print(*A)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n,k = m()

a = l()
dp = [0 for i in range(n)]
ans = [0 for i in range(n)]
for j in range(n):
	po = a[j]
	if j - po < 0:
		dp[0] += 1
	else:
		dp[j-po] += 1
	if j + po + 1 <= n-1:
		dp[j+po+1] -= 1
for j in range(1,n):
	dp[j] += dp[j-1]
if k == 1:
	print(jo(dp))
	exit()
for j in range(n):
	dp[j] += k-2

for j in range(n):
	po = dp[j]
	if j - po < 0:
		ans[0] += 1
	else:
		ans[j-po] += 1
	if j + po + 1 <= n-1:
		ans[j+po+1] -= 1
for j in range(1,n):
	ans[j] += ans[j-1]
print(jo(ans))

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in edge]) for edge in self.edges]):
            print( [[nd for nd,d in edge] for edge in self.edges] )
        else:
            print(self)
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
show_flg=False
show_flg=True
ans=0



n,k=LI()
a=[0]+LI()+[0]
T=min(k,1+int(math.log(2*10**5+1)))

for t in range(T):
    
    nx=[0]*(n+2)
    for i in range(1,n+1):
        l=max(0,i-a[i])
        r=min(i+a[i]+1,n+1)
        nx[l]+=1
        nx[r]+=-1
    #print(a,nx)
    for i in range(n+1):
        nx[i+1]+=nx[i]
    a=nx
print(*a[1:n+1])

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
exit_flag = False

def check_terminate(A):
    for i in range(n):
        if A[i] != n:
            return False
    return True

def one_step(A):
    B = [0] * n
    for i in range(n):
        for j in range(max(0,i-A[i]), min(n-1, i+A[i])+1):
            B[j] += 1
    return B

for i in range(k):
    if not check_terminate(A):
        A = one_step(A)
print(A)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

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


if a.count(0) == n:
    print(*a)
    exit()

for _ in range(k):
    b = [0]*n
    for i in range(n):
        if i-a[i] < 0:
            b[0] += 1
        else:
            b[i-a[i]] += 1
        if i+a[i]+1 < n:
            b[i+a[i]+1] -= 1
    
    judge = True
    tmp = 0
    for i in range(n):
        tmp += b[i]
        a[i] = tmp
        if tmp != n:
            judge = False
    if judge:
        break
print(*a)