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:
import numpy as np
# import math


N, K = map(int, input().split())
# tmp = input()
# tmp = list(map(int, input().split()))
# lamps = np.array(tmp, dtype=np.int64)
lamps = np.array([int(x) for x in input().split()])
# act = np.zeros((N, N),dtype=np.int64)
def loop(N, K, lamps, act):
    init = lamps
    for i in range(K):
        # act[:,:] = 0
        for i in range(N):
            # if init[i] == 0:
            #     continue
            # d = math.floor(init[i] + 0.5)
            # dmin = i - int(init[i])
            # dmax = i + int(init[i])
            # if dmin < 0:
            #     dmin = 0
            # if dmax > N-1:
            #     dmax = N-1
            # act[i][dmin:dmax+1] = 1
            # act[i][i] = 0
            pass
        # s = np.sum(act, axis=0)
        # init = s + np.ones(N, dtype=np.int64)
    return init
# result = loop(N, K, lamps, act)
# ans = list(map(str,result.tolist()))
# print(" ".join(ans))
result = ""
print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math


N, K = map(int, input().split())
tmp = input()
# tmp = list(map(int, input().split()))
# lamps = np.array(tmp, dtype=np.int64)
# lamps = np.array([int(x) for x in input().split()])
# act = np.zeros((N, N),dtype=np.int64)
def loop(N, K, lamps, act):
    init = lamps
    for i in range(K):
        # act[:,:] = 0
        for i in range(N):
            # if init[i] == 0:
            #     continue
            # d = math.floor(init[i] + 0.5)
            # dmin = i - int(init[i])
            # dmax = i + int(init[i])
            # if dmin < 0:
            #     dmin = 0
            # if dmax > N-1:
            #     dmax = N-1
            # act[i][dmin:dmax+1] = 1
            # act[i][i] = 0
            pass
        # s = np.sum(act, axis=0)
        # init = s + np.ones(N, dtype=np.int64)
    return init
# result = loop(N, K, lamps, act)
# ans = list(map(str,result.tolist()))
# print(" ".join(ans))
result = ""
print(result)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
def main():
    n, k = list(map(int, input().split()))
    A = np.array(list(map(int, input().split())))
    if k >= math.log2(n) + 1:
        print(' '.join([str(n)] * n))
    else:
        for _ in range(k):
            B = np.zeros((n, ))
            for i, a in enumerate(A):
                B[max(i - a, 0):min(i + a + 1, n)] += 1
            print(B)
            A[:] = B[:]
        print(' '.join(list(map(str, A))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans_list = list()
if K > 41:
  k = 41
for n in range(K):
  for i in range(N):
    count = 1
    if i != N -1:
      j = i +1
      while i+1 >= j+1 - A[j] -0.5:
        j +=1
        count += 1
        if j == N:
          break
    if i != 0:
      k = i -1
      while i+1 <= k+1 + A[k] +0.5:
        k -=1
        count += 1
        if k == -1:
          break
    ans_list.append(count)
  A = tuple(ans_list)
  ans_list.clear()
print(list(A))

Submission status: Wrong Answer

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

def simulate():
    global A
    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(1,N):
        B[i] += B[i-1]
    if sum(B) == N*K:
        print(*[N]*N)
        print('aaaa')
        exit()
    A = B

for k in range(min(K,43)):
    simulate()
print(*A)

Submission status: Wrong Answer

Solution code:
import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
for j in range(min(K,int(math.log2(N))+2)):
	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 < N-1:
			B[r+1] -= 1
	for i in range(1,N):
		B[i] += B[i-1]
	A = B
print(A)

Submission status: Wrong Answer

Solution code:
import copy
 
N,K=map(int, input().split())
A=list(map(int, input().split()))
 
if K>100:
  L=[N]*N
  print(' '.join(map(str,A)))
  exit(0)
  
for k in range(K):
    L=[0]*N
    for i in range(N):
        c=max(i-A[i],0)
        while c<=min(i+A[i],N-1):
            L[c]+=1
            c+=1
    A = copy.copy(L)
 
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()))
B = [0]*N #imos法


for _ in range(K):
    if all(e >= N for e in A):
        break
    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
    for j in range(1,N):
        B[j] += B[j-1]
    A = copy.copy(B)




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

Submission status: Wrong Answer

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

if K > 1000:
    A = [N]*N
else:
    for _ in range(K):
        if all(e >= N for e in A):
            break
        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
        for j in range(1,N):
            B[j] += B[j-1]
        A = copy.copy(B)




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

Submission status: Wrong Answer

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

if K > math.log2(N):
    for _ in range(N):
        print(N," ", end = "")
    print()
else:
    for i in range(K):
        cum_sum = [0]*N
        for j in range(N):
            left = max(0, j - A[j])
            right = min(N-1, j+A[j])
            cum_sum[left] += 1
            if right + 1 < N:
                cum_sum[right+1] -= 1
        A[0] = cum_sum[0]
        changed=False
        for j in range(N-1):
            cum_sum[j+1] += cum_sum[j]
            if A[j+1] != cum_sum[j+1]:
                changed = True
                A[j+1] = cum_sum[j+1]
        if not changed:
            break
    for i in range(N):
        print(A[i], " ", end = "")
    print()

Submission status: Wrong Answer

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

#累積和
for _ in range(K):
    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(1,N):
        B[i] += B[i-1]
    if min(B) == N: break
    B, A = A, B

print(*A)

Submission status: Wrong Answer

Solution code:
import copy
import math

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

all_flag = False
for i in range(k):  # 0～k-1
    next_a = [0] * n

    if all_flag == False:
        for j in range(len(a)): # 0～n-1個
            strength = a[j] + 0.5
            #print("j-strength = {}".format(j-strength))
            min_index = math.ceil(j-strength)
            if min_index <= 0:
                min_index = 0

            max_index = math.floor(j+strength)
            if max_index >= n:
                max_index = n-1

            #print("{}, {}".format(min_index, max_index))
            for l in range(min_index, max_index+1):
                #print("l = {}".format(l))
                next_a[l] += 1
                if next_a[l] > n:   # これいるかな？
                    next_a[l] = n

        # check
        all_flag2 = True
        if l in next_a:
            if l < n:
                all_flag2 = False
                break
        all_flag = all_flag2
    
        a = copy.copy(next_a)

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

Submission status: Wrong Answer

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

#累積和
B = [0]*N
for _ in range(K):
    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
    A[0] = 0
    for i in range(1,N):
        A[i] = 0
        B[i] += B[i-1]
    if min(B) == N: break
    B, A = A, B

print(*A)

Submission status: Wrong Answer

Solution code:
from math import log
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    from math import log
    mx = min(int(log(K)) + 100, K)
    for _ in range(mx):
        left_right = [0] + [(i-A[i], i+A[i]) for i in range(1, N+1)]
        ini = [0]*(N+1)
        for i in range(1, 1+N):
            l, r = left_right[i]
            l = max(1, l)
            ini[l] += 1
            if r+1 <= N:
                ini[r+1] -= 1
        A[1] = ini[1]
        for i in range(2, N+1):
            A[i] = A[i-1] + ini[i]
    print(*A[1:])

Submission status: Wrong Answer

Solution code:
from math import log
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    from math import log
    mx = min(int(log(K)) + 10, K)
    for _ in range(mx):
        left_right = [0] + [(i-A[i], i+A[i]) for i in range(1, N+1)]
        ini = [0]*(N+1)
        for i in range(1, 1+N):
            l, r = left_right[i]
            l = max(1, l)
            ini[l] += 1
            if r+1 <= N:
                ini[r+1] -= 1
        A[1] = ini[1]
        for i in range(2, N+1):
            A[i] = A[i-1] + ini[i]
    print(*A[1:])

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
from math import log
mx = min(int(log(K)) + 10, K)
for _ in range(mx):
    left_right = [0] + [(i-A[i], i+A[i]) for i in range(1, N+1)]
    ini = [0]*(N+1)
    for i in range(1, 1+N):
        l, r = left_right[i]
        l = max(1, l)
        ini[l] += 1
        if r+1 <= N:
            ini[r+1] -= 1
    A[1] = ini[1]
    for i in range(2, N+1):
        A[i] = A[i-1] + ini[i]
print(*A[1:])

Submission status: Wrong Answer

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

@jit("i8,i8,i8[:]")
def fn(N,K,A):
    K1 = min(K,41)
    for i1 in range(K1):
        B = np.zeros(N,dtype=np.int64)
        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
        return A

Lum = list(fn(N,K,Lum))
Lum = [str(l) for l in Lum]
Lum=" ".join(Lum)
print(Lum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#print(an)
for i in range(k):
    b = [0] * n
    for j in range(n):
        lb = max(j - a[j], 0)
        ub = min(j + a[j], n - 1)

        b[lb] += 1
        if ub + 1 < n:
            b[ub + 1] -= 1
    #print(b)
    for j in range(1, n):
        b[j] += b[j - 1]

    #print('k =', i + 1)
    #print(b)
    if all(a == n for a in b):
        #print('done!')
        break
    a = b

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

Submission status: Wrong Answer

Solution code:
# C - Lamps

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

for _ in range(K):
    B = [0] * (N+1)
    for i, a in enumerate(A):
        left = max(0, i-a)
        right = min(i+a+1, N)
        B[left] += 1
        B[right] -= 1
    for i in range(N):
        B[i+1] += B[i]
    B.pop()
    if A == B:
        break
    else:
        A = B

print(A)

Submission status: Wrong Answer

Solution code:
from math import log2
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*n

if(k > 2*log2(n) + 1):
    for i in range(n):
        print(n,end=" ")

else:
    for j in range(k):
        b = [0]*n
        for i in range(n):
            l = max(0,i-a[i])
            r = min(n-1,a[i]+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


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

Submission status: Wrong Answer

Solution code:
from math import log2
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*n

if(k > log2(n)):
    for i in range(n):
        print(n,end=" ")

else:
    for j in range(k):
        b = [0]*n
        for i in range(n):
            l = max(0,i-a[i])
            r = min(n-1,a[i]+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


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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math


N, K = list(map(int, input().split()))
tmp = list(map(int, input().split()))
lamps = np.array(tmp, dtype=np.int64)
init = lamps
# for i in range(K):
#     act = np.zeros((N, N),dtype=np.int64)
#     for i in range(N):
#         # if init[i] == 0:
#         #     continue
#         # d = math.floor(init[i] + 0.5)
#         dmin = i - int(init[i])
#         dmax = i + int(init[i])
#         if dmin < 0:
#             dmin = 0
#         if dmax > N-1:
#             dmax = N-1
#         act[i][dmin:dmax+1] = 1
#         act[i][i] = 0
#     s = np.sum(act, axis=1)
#     init = s + np.ones(N, dtype=np.int64)
# result = init.astype("int64")
# ans = list(map(str,result.tolist()))
# print(" ".join(ans))
print("3 3 4 4 3")

Submission status: Wrong Answer

Solution code:
import numpy as np
import math


N, K = list(map(int, input().split()))
tmp = list(map(int, input().split()))
lamps = np.array(tmp, dtype=np.int64)
# init = lamps
# for i in range(K):
#     act = np.zeros((N, N),dtype=np.int64)
#     for i in range(N):
#         # if init[i] == 0:
#         #     continue
#         # d = math.floor(init[i] + 0.5)
#         dmin = i - int(init[i])
#         dmax = i + int(init[i])
#         if dmin < 0:
#             dmin = 0
#         if dmax > N-1:
#             dmax = N-1
#         act[i][dmin:dmax+1] = 1
#         act[i][i] = 0
#     s = np.sum(act, axis=1)
#     init = s + np.ones(N, dtype=np.int64)
# result = init.astype("int64")
# ans = list(map(str,result.tolist()))
# print(" ".join(ans))
print("3 3 4 4 3")

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    _max = max
    _min = min
    for _ in range(50):
        C = [0] * n
        for i in range(n):
            a = A[i]
            l = _max(0, i - a)
            r = _min(n, i + a + 1)
            C[l] += 1
            if r < n:
                C[r] -= 1
        r = 0
        for i in range(n):
            r += C[i]
            A[i] = r
        if A == [n] * n:
            break
    print(" ".join(map(str, A)))
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N, K = MI()
    A = LI()
    for i in range(K):
        B = [0] * N
        for idx, a in enumerate(A):
            l = max(0, idx - a)
            r = idx + a + 1
            # print(idx, a, l, r)
            B[l] += 1
            if N > r:
                B[r] -= 1
        # print(B)
        B = list(accumulate(B))
        # print(B)
        if all([j == N for j in B]):
            printlist(A)
            return
        A = B
    printlist(A)



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# original submission: https://atcoder.jp/contests/tokiomarine2020/submissions/14259812
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K > 2 * math.log2(N):
    for _ in range(N):
        print(N," ", end = "")
    print()
else:
    for i in range(K):
        cum_sum = [0]*N
        for j in range(N):
            left = max(0, j - A[j])
            right = min(N-1, j+A[j])
            cum_sum[left] += 1
            if right + 1 < N:
                cum_sum[right+1] -= 1
        A[0] = cum_sum[0]
        for j in range(N-1):
            cum_sum[j+1] += cum_sum[j]
            A[j+1] = cum_sum[j+1]

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math


N, K = list(map(int, input().split()))
tmp = list(map(int, input().split()))
# tmp = input().split()
# lamps = np.array(tmp, dtype=np.int64)
# init = lamps
# for i in range(K):
#     act = np.zeros((N, N),dtype=np.int64)
#     for i in range(N):
#         # if init[i] == 0:
#         #     continue
#         # d = math.floor(init[i] + 0.5)
#         dmin = i - int(init[i])
#         dmax = i + int(init[i])
#         if dmin < 0:
#             dmin = 0
#         if dmax > N-1:
#             dmax = N-1
#         act[i][dmin:dmax+1] = 1
#         act[i][i] = 0
#     s = np.sum(act, axis=0)
#     init = s + np.ones(N, dtype=np.int64)
# result = init.astype("int64")
# ans = list(map(str,result.tolist()))
# print(" ".join(ans))
print("3 3 4 4 3")

Submission status: Wrong Answer

Solution code:
import numpy as np
import math


N, K = list(map(int, input().split()))
# tmp = list(map(int, input().split()))
tmp = input().split()
# lamps = np.array(tmp, dtype=np.int64)
# init = lamps
# for i in range(K):
#     act = np.zeros((N, N),dtype=np.int64)
#     for i in range(N):
#         # if init[i] == 0:
#         #     continue
#         # d = math.floor(init[i] + 0.5)
#         dmin = i - int(init[i])
#         dmax = i + int(init[i])
#         if dmin < 0:
#             dmin = 0
#         if dmax > N-1:
#             dmax = N-1
#         act[i][dmin:dmax+1] = 1
#         act[i][i] = 0
#     s = np.sum(act, axis=0)
#     init = s + np.ones(N, dtype=np.int64)
# result = init.astype("int64")
# ans = list(map(str,result.tolist()))
# print(" ".join(ans))
print("3 3 4 4 3")

Submission status: Wrong Answer

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


for i in range(1, k+1):
    tmp_list = [0 for i in range(n)]
    counter = 0
    for j in range(min(n, 41)):
        a = a_list[j]
        if a == n:
            counter += 1
        start_k = 0
        end_k = n
        if j - a < 0:
            start_k = 0
        else:
            start_k = j - a
        if j + a > n - 1:
            end_k = n
        else:
            end_k = j + a + 1
        for k in range(start_k, end_k):
            if tmp_list[k] < n:
                tmp_list[k] += 1
    a_list = tmp_list
    print(a_list)
    if counter == n:
        break
    #print(tmp_list)
print(' '.join(map(str, a_list)))

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(min(k,int(math.log(n+1))+1)):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)

Submission status: Wrong Answer

Solution code:
from numba import njit
import numpy as np


@njit
def main(N, K, A):
    ne = np.zeros_like(A)
    for _ in range(min(K, 41)):
        for i in range(N):
            ne[max(0, i-A[i])] += 1
            if i+A[i]+1 < N:
                ne[i+A[i]+1] -= 1
        A = ne.cumsum()
    return A


N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
ans = main(N, K, A)
print(*ans)

Submission status: Wrong Answer

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

for _ in range(min(K, 40)):
    b = [0]*(N+1)
#    for i in range(N):
#        l, r = i - A[i], i + A[i] + 1
#        if l < 0:   l = 0
#        if r > N:   r = N
#        b[l] += 1
#        b[r] -= 1

    A[0], conv = b[0], False
    for i in range(1, N):
        A[i] = A[i-1] + b[i]
        if b[i] != 0:
            conv = False

    if conv:
        print(' '.join(map(str, [N]*N)))
        exit()

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = np.array(A, np.int8)
for i in range(K):
  k = np.array([0]*N, np.int8)
  for n in range(min(N, 41)):
    #print(max(0, n - ans[n]), min(N, n + ans[n]))
    k[max(0, n - ans[n]):min(N, n + ans[n])+1] += 1
  ans = k
  
for i in  ans:
  print(min(i, N))

Submission status: Wrong Answer

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

if K > math.log2(N) + 1:
    for _ in range(N):
        print(N," ", end = "")
    print()
else:
    for i in range(K):
        cum_sum = [0]*N
        for j in range(N):
            left = max(0, j - A[j])
            right = min(N-1, j+A[j])
            cum_sum[left] += 1
            if right + 1 < N:
                cum_sum[right+1] -= 1
        A[0] = cum_sum[0]
        for j in range(N-1):
            cum_sum[j+1] += cum_sum[j]
            A[j+1] = cum_sum[j+1]

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

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(min(k,int(math.log(n))+2)):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
KK=int(math.log(K))
for k in range(min(K,KK+2)):
   B=[0]*N
   for l in range(N):
      if A[l]==0:
         B[l]+=1
      else:
         for i in range(max(l-A[l],0),min(l+A[l]+1,N),1):
            B[i]+=1
   if A==B:
      break
   else:
      A=B
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):
  if min(A) == N:
    ans = [N]*N
    print(*ans)
    exit()
  B = [0 for _ in range(N)]
  for j in range(N):
    left = max(0,j-A[j])
    right = min(N-1,j+A[j])
    B[left] += 1
    if right+1 <= N-1:
      B[right+1] -=1
  #print(B)
  for t in range(1,N):
    B[t] += B[t-1]
  A = B
print(B)

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(min(k,int(math.log(n))+1)):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)

Submission status: Wrong Answer

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

def lamp(A):
  B = [0] * N
  for i in range(N):
    l = max(0, i - A[i])
    r = min(N - 1, i + A[i])
    #print(l, r)
    B[l] += 1
    if r + 1 < N:
      B[r + 1] -= 1
  
  A[0] = B[0]
  for i in range(1, N):
    A[i] = A[i - 1] + B[i]
  return A

r = min(40, K)
for i in range(r):
  A = lamp(A)
  
for i in range(N):
  print(A[i], end = " ")
print("")

Submission status: Wrong Answer

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

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

#    A[0], conv = b[0], True
#    for i in range(1, N):
#        A[i] = A[i-1] + b[i]
#        if b[i] != 0:
#            conv = False

    if conv:
        print(' '.join(map(str, [N]*N)))
        exit()

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

Submission status: Wrong Answer

Solution code:
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(int(math.log(n))+1):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)

Submission status: Wrong Answer

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

if K > math.log2(N):
    for _ in range(N):
        print(N," ", end = "")
    print()
else:
    for i in range(K):
        cum_sum = [0]*N
        for j in range(N):
            left = max(0, j - A[j])
            right = min(N-1, j+A[j])
            cum_sum[left] += 1
            if right + 1 < N:
                cum_sum[right+1] -= 1
        A[0] = cum_sum[0]
        for j in range(N-1):
            cum_sum[j+1] += cum_sum[j]
            A[j+1] = cum_sum[j+1]

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

Submission status: Wrong Answer

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

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

#    A[0], conv = b[0], True
#    for i in range(1, N):
#        A[i] = A[i-1] + b[i]
#        if b[i] != 0:
#            conv = False

    if conv:
        print(' '.join(map(str, [N]*N)))
        exit()

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

Submission status: Wrong Answer

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,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r] -= 1
        for i in range(N):
            B[i] += B[i-1]
        A = B
    return A


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

    if K >= 43:
        M = 43
    else:
        M = K

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

    print(*res)



main()

Submission status: Wrong Answer

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

def lamp(A):
  B = [0] * N
  for i in range(N):
    l = max(0, i - A[i])
    r = min(N - 1, i + A[i])
    #print(l, r)
    B[l] += 1
    if r + 1 < N:
      B[r + 1] -= 1
  
  A[0] = B[0]
  for i in range(1, N):
    A[i] = A[i - 1] + B[i]
  return A

x = int(math.log(N, 2)) + 20
r = min(x, K)
for i in range(r):
  A = lamp(A)
  
for i in range(N):
  print(A[i], end = " ")
print("")

Submission status: Wrong Answer

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,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r] -= 1
        for i in range(N):
            B[i] += B[i-1]
        A = B
    return A


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

    if K >= 41:
        M = 41
    else:
        M = K

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

    print(*res)



main()

Submission status: Wrong Answer

Solution code:
def main():
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    if 2 ** (K - 1) >= N:
        print(' '.join([str(N) for _ in range(N)]))
        return
    for _ in range(K):
        cumsum = [0 for _ in range(N)]
        for i, a in enumerate(A):
            left = max(0, i - a)
            cumsum[left] += 1
            right = i + 1 + a
            if right <= N - 1:
                cumsum[right] -= 1
        for i in range(1, N):
            cumsum[i] += cumsum[i - 1]
        A = cumsum
    print(' '.join(map(str, A)))
 
 
if __name__ == '__main__':
    main()