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
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size,init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]



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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x,A):
    n=len(x)
    res=[-1]*n
    for i in range(n):

        res[i]=x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b=bin(b)
        tmp=b[2:].zfill(digit)
        yield list(map(int,tmp))
        #b=list(map(int,list(b[2:].zfill(digit))))
        #yield b
        

def search(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,K=acinput()
A=acinput()


Al=[0]*(N+1)

if K>1:
    for i in range(N):    
        d=max(A[i]+K-2,0)
        #print(Al,i,d)
        l=max(i-d,0)
        r=min(i+d,N-1)
        print(i,d,l,r)
        Al[l]+=1
        Al[r+1]-=1
    Al=np.cumsum(Al)
        
else:
    Al[:N]=A




B=Al
res=[0]*(N+1)

for i in range(N):
    d=B[i]
    l=max(i-d,0)
    r=min(i+d,N-1)
    res[l]+=1
    res[r+1]-=1
    
    
print(" ".join(map(str,list(np.cumsum(res)[:N]))))

#print(B)
#print(res)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
A = list(map(int,input().split()))
B = [int(0) for d in range(n)]
for i in range(k):
    for j in range(n):
        if int(A[j]) >= 1:
            min = (j+1) - int(A[j])
            max = (j+1) + int(A[j]) 
            for e in range(n):
                if min <= e or e <= max:
                    B[e] = int(B[e]) + 1
        min = 0
        max = 0

Submission status: Wrong Answer

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


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [0] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def _add_topdown(self, a, b, value, k=1, l=0, r=-1):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r == -1:
            r = self.offset
        if r <= a or b <= l:
            return
        if l == r - 1:
            self.st[k] += value
            return
        if a <= l and r <= b:
            self.st[k] += value
            return
        mid = (l + r) // 2
        self._add(a, b, value, k * 2, l, mid)
        self._add(a, b, value, k * 2 + 1, mid, r)

    def _add_bottomup(self, a, b, value):
        """区間[a, b) に対する加算
        """
        a += self.offset
        b += self.offset - 1
        while a < b:
            if a & 1:
                self.st[a] += value
                a += 1
            a >>= 1
            if not b & 1:
                self.st[b] += value
                b -= 1
            b >>= 1
        if a == b:
            self.st[a] += value

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._add_bottomup(a, b, value)

    def get(self, key):
        """値の取得"""
        offset = len(self.st) // 2
        k = offset + key
        v = self.st[k]
        k >>= 1
        while k > 0:
            v += self.st[k]
            k >>= 1
        return v


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    KL = N.bit_length() * 2
    if K > KL:
        print(*([N] * N))
        return
    raq = RAQ.from_array(A)
    a = [0 for i in range(N)]

    for k in range(min(K, KL)):
        for i in range(N):
            a[i] = raq.get(i)
            raq.add(i, i+1, -a[i])
        for i in range(N):
            l = max(0, i-a[i])
            r = min(N, i+1+a[i])
            raq.add(l, r, 1)
    print(*[raq.get(i) for i in range(N)])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
i=(input().split())
j=(input().split())

N=int(i[0])
K=int(i[1])

e=[]
f=[]

for z in range(K):
    f=[]
    for x in range(N):
        d=[]
        for y in range(N):
            if abs(x-y) <= int(j[y]):
                d.append(1)
            elif abs(x-y) > int(j[y]):
                d.append(0)
        f.append(sum(d))
    j=f
    
    
print(f)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    ans_list = [0] * n

    if k > 10**2:
        print([n]*n)
        exit()

    for i in range(k):
        if i % 2 != 0:
            if ans_list.count(n) == n:
                print(*ans_list)
                exit()
            num_list = [0] *n  
            for j in range(n):
                for w in range(ans_list[j]+1):
                    if w == 0:
                        num_list[j] += 1
                    else:
                        if j + w < n:
                            num_list[j+w] += 1
                        if j - w >= 0:
                            num_list[j-w] += 1
        else:
            if num_list.count(n) == n:
                print(*num_list)
                exit()
            ans_list = [0] *n  
            for j in range(n):
                for w in range(num_list[j]+1):
                    if w == 0:
                        ans_list[j] += 1
                    else:
                        if j + w < n:
                            ans_list[j+w] += 1
                        if j - w >= 0:
                            ans_list[j-w] += 1

    if k % 2 == 0:
        print(*num_list)
    else:
        print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
if max(A)==0:
  ans1=[0]*n
  print(' '.join(map(str, ans1)))
  exit()
if k>=n-1:
  ans2=[n]*n
  print(' '.join(map(str, ans2)))
  exit()
def sousa(a,k):
  B=[0]*len(a)
  for i in range(1,len(a)+1):#1~N
    for j in range(i-a[i-1],i+a[i-1]+1):
      if j>0 and j<=len(a):
        B[j-1]+=1#0~N-1
  k-=1
  return B if k==0 else sousa(B,k)
print(' '.join(map(str, sousa(A,k))))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

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

def get_range(n, A):
    add_area_min = math.ceil(max(n - A[n] - 0.5, 0))
    add_area_max = int(min(n + A[n] + 0.5, N-1))    
    return add_area_min, add_area_max
    
for k in range(K):
    for n in range(N):
        if A[n] != 0:
            # 照らしている箇所
            add_area_min, add_area_max = get_range(n, A)
            print("debug:", n, add_area_min, add_area_max)
            A_num[add_area_min: add_area_max+1] += 1 
            A_num[n] -= 1
    # 強さを更新
    A = [ A_num[i] if A_num[i] != 1 else A[i] for i in range(N)]
    # 初期化
    A_num = np.ones(N, dtype=int)
print(' '.join(map(str, A)))

Submission status: Wrong Answer

Solution code:
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))
imos = [0]*(N+1)
for i, ai in enumerate(A):
    imos[max(0, i-ai)] += 1
    imos[min(N, i+ai+1)] -= 1
ans = [imos[0]]
for i in range(1, N):
    ans += [imos[i]+ans[i-1]]
if K == 1:
    print(' '.join(map(str, ans)))
    sys.exit()
imos = [0]*(N+1)
for i, ai in enumerate(ans):
    imos[max(0, i-ai)] += 1
    imos[min(N, i+ai+1)] -= 1
ans = [imos[0]]
for i in range(1, N):
    ans += [imos[i]+ans[i-1]]
if K == 2:
    print(' '.join(map(str, ans)))
    sys.exit()
Km3 = K-3
imos = [0]*(N+1)
for i, ai in enumerate(ans):
    imos[max(0, i-ai-Km3)] += 1
    imos[min(N, i+ai+Km3+1)] -= 1
ans = [imos[0]]
for i in range(1, N):
    ans += [imos[i]+ans[i-1]]
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
N_K = input().split()
N = int(N_K[0])
K = int(N_K[1])
A = input().split()
A = [int(i) for i in A]

for k in range(K):
    P = [0]*N
    for a in range(N):
        x = int(a+1-A[a]-0.5)
        y = int(a+1+A[a]+0.5)
        if x < 0:
            x = 0
        elif y > N:
            y = N
        P[x:y] = [j+1 for j in P[x:y]]
    if A == P:
        break
    A = P
    print(' '.join(map(str,P)))

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] * N
    for i in range(N):
        d = A[i]
        B[i] += 1
        for j in range(d):
            if i + j+1 < N:
                B[i + j+1] += 1
            if i > j:
                B[i - j - 1] += 1
    for i in range(N):
        A[i] = B[i]


print(A)

Submission status: Wrong Answer

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

print(s)

Submission status: Wrong Answer

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


class RAQ():
    
    def __init__(self, size):
        """初期化"""
        self.size = size
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [0] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a):
        st = cls(len(a))
        for i, x in enumerate(a):
            st.add(i, i+1, x)
        return st

    def _add_topdown(self, a, b, value, k=1, l=0, r=-1):
        """区間[a, b) に対する加算
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r == -1:
            r = self.offset
        if r <= a or b <= l:
            return
        if l == r - 1:
            self.st[k] += value
            return
        if a <= l and r <= b:
            self.st[k] += value
            return
        mid = (l + r) // 2
        self._add(a, b, value, k * 2, l, mid)
        self._add(a, b, value, k * 2 + 1, mid, r)

    def _add_bottomup(self, a, b, value):
        """区間[a, b) に対する加算
        """
        a += self.offset
        b += self.offset - 1
        while a < b:
            if a & 1:
                self.st[a] += value
                a += 1
            a >>= 1
            if not b & 1:
                self.st[b] += value
                b -= 1
            b >>= 1
        if a == b:
            self.st[a] += value

    def add(self, a, b, value):
        """区間[a, b) に対する加算"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._add_bottomup(a, b, value)

    def get(self, key):
        """値の取得"""
        offset = len(self.st) // 2
        k = offset + key
        v = self.st[k]
        k >>= 1
        while k > 0:
            v += self.st[k]
            k >>= 1
        return v


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def solve(N, K, A):
    KL = int(math.log2(N) * 2) + 3
    if K > KL:
        print(*([N] * N))
        return
    raq = RAQ.from_array(A)
    a = [0 for i in range(N)]

    for k in range(min(K, KL)):
        for i in range(N):
            a[i] = raq.get(i)
            raq.add(i, i+1, -a[i])
        for i in range(N):
            l = max(0, i-a[i])
            r = min(N, i+1+a[i])
            raq.add(l, r, 1)
    print(*[raq.get(i) for i in range(N)])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
i=(input().split())
j=(input().split())

N=i[0]
K=i[1]

e=[]
f=[]

for z in range(int(K)):
    f=[]
    for x in range(int(N)):
        d=[]
        for y in range(int(N)):
            if abs(x-y) <= int(j[y]):
                d.append(1)
            elif abs(x-y) > int(j[y]):
                d.append(0)
        f.append(sum(d))
    j=f
    
    
print(f)

Submission status: Wrong Answer

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

if K>=N:
    A=[N]*N
    print(" ".join(str(x) for x in A))
    exit()

for i in range(K):
    cnt=[0]*N
    if min(A)==N:
        A=[N]*N
        print(" ".join(str(x) for x in A))
        exit()
    for j in range(N):
        p=A[j]
        for k in range(max(0,j-p),min(j+p+1,N)):
                cnt[k]+=1
    A=cnt
    print(A)

print(" ".join(str(x) for x in 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 = [1] * n
  i = 0
  while i < n - 1:
    j = 1
    while j <= ds[i]:
      if i + j > n - 1:
        break 
      tmpds[i + j] += 1
      j += 1
    i += 1

  i = n - 1
  while i > 0:
    j = 1
    while j <= ds[i]:
      if i - j <= 0:
        break
      tmpds[i - j] += 1
      j += 1
    i -= 1

  ds = tmpds.copy()
  if ds.count(n) == n:
    break
  t += 1

dsstr = map(str, ds)
ans = " ".join(dsstr)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
#A = np.array([0] * N)
#print(A)
cnt = 0

for _ in range(K):
  B = np.array([0] * N)
  stop = 0
  for i in range(N):
    p = A[i]
    L = max(i-p, 0)
    R = min(i+p, N-1)
    for j in range(L, R+1):
      B[j] += 1
      if B[j] == N:
        stop += 1
  cnt += 1
  A = B
  #print(A)
  if stop == N:
    #print(cnt)
    break

print(A)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    ans_list = [0] * n

    if k > 10**4:
        print([n]*n)
        exit()

    for i in range(k):
        if i % 2 != 0:
            if ans_list.count(n) == n:
                print(*ans_list)
                exit()
            num_list = [0] *n  
            for j in range(n):
                for w in range(ans_list[j]+1):
                    if w == 0:
                        num_list[j] += 1
                    else:
                        if j + w < n:
                            num_list[j+w] += 1
                        if j - w >= 0:
                            num_list[j-w] += 1
        else:
            if num_list.count(n) == n:
                print(*num_list)
                exit()
            ans_list = [0] *n  
            for j in range(n):
                for w in range(num_list[j]+1):
                    if w == 0:
                        ans_list[j] += 1
                    else:
                        if j + w < n:
                            ans_list[j+w] += 1
                        if j - w >= 0:
                            ans_list[j-w] += 1

    if k % 2 == 0:
        print(*num_list)
    else:
        print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))

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

    flag = False
    for i in range(1,k+1):
        pos = [n]*n
        neg = [n]*n

        for j in range(n):
            pwr = dp[i-1][j]
            pos[max(0,j-pwr)]+=1
            neg[min(n-1,j+pwr)]+=1

        ac_pos = 0
        ac_neg = 0
        for j in range(n):
            ac_pos += pos[j]
            if ac_pos == n:
                break
            pos[j] = ac_pos

        for j in range(n):
            ac_neg += neg[j]
            if ac_neg == n:
                break
            neg[j] = ac_neg
            
        if pos[0]==n and neg[n-1]==n:
            flag = True
            break

        dp[i][0] = pos[0]
        for j in range(1,n):
            dp[i][j] = pos[j] - neg[j-1]
    
    if flag:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()

Submission status: Wrong Answer

Solution code:
x=input()
x0=x.split()
n=int(x0[0])
k=int(x0[1])
a0=input()
a0=a0.split()
a=[int(s) for s in a0]
a1=[int(s) for s in a0]
for f in range(k):
    for x in range(n):
        c=0
        for i in range(n):
            if a1[i]-abs(x-i)>=0:
                c=c+1
        a[x]=c
    a1=[int(s) for s in a]
print(a)

Submission status: Wrong Answer

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

temp=A
max_pow=0

for i in range(K):
  max_pow=max(A)
  temp=[0]*N
  for j in range(N):
    for k in range(-max_pow,max_pow+1):
      if(j+k>=0 and j+k<=len(A)-1):
        if(A[j+k]>=abs(k)):
          temp[j]=temp[j]+1
  A=temp

print(A)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
import numpy as np
import math
if K >= 1+math.log2(N):
    A = [N]*N
else:
    A = np.array(A)
    for _ in range(K):
        B = A
        A = np.zeros(N)
        for i in range(N):
            b = B[i]
            l, r = int(max(0, i-b)), int(min(N, i+b+1))
            C, D = np.ones(N), np.ones(N)
            C[:l], D[:r] = 0, 0
            A += C-D
print(' '.join(map(str, list(map(int, A)))))

Submission status: Wrong Answer

Solution code:
#C - Lamps
N,K= map(int,input().split())
A = list(map(int, input().split()))
# DP = [0]*N
# DP2 = [0]*N
DP = [0]*N
DP2 = [[0] *N for p in range(N)]
for _ in range(K):
    for i in range(N):
        for j in range(A[i],-A[i]-1,-1):
            if A[i] == 0:
                DP[i] += 1
            else:
                pass
            if i != i-j and i-j >= 0 and i-j < N and DP2[i-j][i] ==0:
                DP[i-j] += 1
                DP2[i-j][i] = 1

            else:
                pass
    #print(DP)
    for k in range(len(DP)):
        A[k] += DP[k]
    DP = [0]*N
    #print(DP2)
    print(A)

print(A)

Submission status: Wrong Answer

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

if K >= N:
    print(*([N]*N))
    exit()

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = i_map()
    num_list = i_list()

    ans_list = [0] * n

    if k > 10**3:
        print([n]*n)
        exit()

    for i in range(k):
        if i % 2 != 0:
            if ans_list.count(n) == n:
                print(*ans_list)
                exit()
            num_list = [0] *n  
            for j in range(n):
                for w in range(ans_list[j]+1):
                    if w == 0:
                        num_list[j] += 1
                    else:
                        if j + w < n:
                            num_list[j+w] += 1
                        if j - w >= 0:
                            num_list[j-w] += 1
        else:
            if num_list.count(n) == n:
                print(*num_list)
                exit()
            ans_list = [0] *n  
            for j in range(n):
                for w in range(num_list[j]+1):
                    if w == 0:
                        ans_list[j] += 1
                    else:
                        if j + w < n:
                            ans_list[j+w] += 1
                        if j - w >= 0:
                            ans_list[j-w] += 1

    if k % 2 == 0:
        print(*num_list)
    else:
        print(*ans_list)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time
from decimal import *


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def pl(x, d):
    return x - d - 0.5


def pr(x, d):
    return x + d + 0.5


def b(A, K):
    for k in range(K):
        ans = []
        for i in range(len(A)):
            c = 0
            for j in range(len(A)):
                l = pl(j, A[j])
                r = pr(j, A[j])

                if i >= l and i <= r:
                    c += 1
            ans.append(c)
        A = ans
        if ans[-1] == len(A):
            print(k, ans)
            return ans
    return A

def main():
    N, K = MI()
    A = LI()
    # N = 100000
    # A = [0] * N
    l_arr = []
    r_arr = []

    # print(b(A, K))

    for i in range(N):
        l = pl(i, A[i])
        r = pr(i, A[i])
        l_arr.append((l, r))
        r_arr.append((r, l))
        # c = r - l
        # v.append(math.ceil(c))
        # print(i+1, 'left', pl(i+1, A[i]), 'right', pr(i+1, A[i]))

    l_arr.sort()
    r_arr.sort()
    # print('l_arr', l_arr)
    # print('r_arr', r_arr)

    ans = [0] * N

    for k in range(K):
        nl_arr = []
        nr_arr = []
        for i in range(N):
            l_idx = bisect.bisect_right(l_arr, (i, None))
            r_idx = bisect.bisect_right(r_arr, (i, None))
            ans[i] = l_idx - r_idx
            l = pl(i, ans[i])
            r = pr(i, ans[i])
            nl_arr.append((l, r))
            nr_arr.append((r, l))

        # nl_arr.sort()
        # nr_arr.sort()
        l_arr = nl_arr
        r_arr = nr_arr

        # print(k, ans[-1])
        if ans[-1] == N:
            break
        # print(idx, l_arr[idx])
        # print(*ans)
    # print(*A)
    # print(k)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

INF = 2**31-1


N, k = map(int, input().split())
prev_arr = list(map(int, input().split()))

for i in range(min(k, 3*int(math.log(N))+1)):
    que = []
    arr = [0]*N
    for j in range(N):
        heapq.heappush(que, j+prev_arr[j])
        while que[0] < j:
            heapq.heappop(que)
        arr[j] += len(que)
    # print(arr)

    que = []
    for j in reversed(range(N)):
        heapq.heappush(que, -(j-prev_arr[j]))
        while -que[0] > j:
            heapq.heappop(que)
        arr[j] += len(que) - 1

    prev_arr = arr

print(*prev_arr)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,k = map(int,input(). split ())
a = list(map(int, input().split()))
b = [0] * n
for m in range(k):
    for i in range(n):
        j = a[i]
        # print(j)
        for jj in range(j+1):
            # print(i-jj)
            if jj == 0:
                b[i] += 1
            else:
                if i-jj >= 0:
                    b[i-jj] += 1
                if n-1 >= i+jj:
                    b[i+jj] += 1
        # print(b)

    # for l in range(n):
    #     a[l] = b[l] 
    a = b
    
    b = [0] * n

print(a)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
if max(A)==0:
  for y in range(n):
    print(0,end=" ")
  exit()
if k>=n-1:
  for y in range(n):
    print(n,end=" ")
  exit()
def sousa(a,k):
  B=[0]*len(a)
  for i in range(1,len(a)+1):#1~N
    for j in range(i-a[i-1],i+a[i-1]+1):
      if j>0 and j<=len(a):
        B[j-1]+=1#0~N-1
  k-=1
  return B if k==0 else sousa(B,k)
for x in sousa(A,k):
  print(x,end=" ")

Submission status: Wrong Answer

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

light_range = lambda x,d:[math.ceil(x-d-0.5) if (x-d-0.5) >= 0 else 0,math.floor(x+d+0.5)]

def update_lights(a_):
    light_nums = [0] * n
    light_ranges = [light_range(x+1,d) for x,d in enumerate(a_)]
    for x_, light_range_ in enumerate(light_ranges):
        for r in range(light_range_[0],int(light_range_[1])+1):
            if (r>=1 and r <= len(light_nums)): light_nums[r-1] += 1 
    return light_nums

updated_a = a
for _ in range(k):
    _a = updated_a
    updated_a = update_lights(_a)
print(updated_a)

Submission status: Wrong Answer

Solution code:
N,K = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [0] * N
if K*N >= 10**5:
    ans = [N] * N
    for i in range(N):
        print(ans[i],end=" ")
        exit()
for i in range(K):
    for j in range(N):
        b[j] = a[j]
    a = [0] * N
    for j in range(N):
        for k in range(max(0,j-b[j]),min(j+b[j],N-1)+1):
            a[k] += 1
for i in range(N):
    print(a[i],end=" ")

Submission status: Wrong Answer

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

A_i = [0 for a in range(len(A))]
for i in range(K):
  for j in range(N):
    for k in range(A[j]):
      if j-A[j]+k >= 0:
        A_i[j-A[j]+k] = A_i[j-A[j]+k] + 1
      if j+k+1 < len(A):
        A_i[j+k+1] = A_i[j+k+1] + 1
    A_i[j] = A_i[j] + 1
  A = A_i
  A_i = [0 for a in range(len(A))]

print(A)