Problem:


Score : 500 points

Problem Statement

We have N bulbs arranged on a number line, numbered 1 to N from left to right.
Bulb i is at coordinate i.

Each bulb has a non-negative integer parameter called intensity.
When there is a bulb of intensity d at coordinate x, the bulb illuminates the segment from coordinate x-d-0.5 to x+d+0.5.
Initially, the intensity of Bulb i is A_i. We will now do the following operation K times in a row:

For each integer i between 1 and N (inclusive), let B_i be the number of bulbs illuminating coordinate i. Then, change the intensity of each bulb i to B_i.

Find the intensity of each bulb after the K operations.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq K \leq 2 \times 10^5

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the intensity A{'}_i of each bulb i after the K operations to Standard Output in the following format:

A{'}_1 A{'}_2 \ldots A{'}_N

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

Initially, only Bulb 1 illuminates coordinate 1, so the intensity of Bulb 1 becomes 1 after the operation.
Similarly, the bulbs initially illuminating coordinate 2 are Bulb 1 and 2, so the intensity of Bulb 2 becomes 2.

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

def light(a_list):
    outcome= np.array([0]*(n+1))
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

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

[print(aa,end=' ') for aa in a]

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        B = [0 for _ in range(N)]
        count = 0
        for i in range(N):
            if A[i] == N:
                count += 1
            l = max(0, i - A[i])
            r = min(N - 1, i + A[i])
            B[l] += 1
            if r + 1 < N:
                B[r + 1] -= 1
        B = list(accumulate(B))
        if count == N:
            break
        else:
            A = B
    print(*B, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if k >= 50:
    k = 50

dp = [[0] * 2 for i in range(n)]

ans = l[:]

for i in range(k):
    for j in range(n):
        tmp = ans[j] + 0.5
        dp[j][0] = (j+1 - tmp)
        dp[j][1] = (j+1 + tmp)

    ans = [0] * n

    for x in range(n):
        for y in range(n):
            if dp[y][0] <= x+1 <= dp[y][1]:
                ans[x] += 1

else:
    print(*ans)

Submission status: Time Limit Exceeded

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

if k >= 100:
    k = 100

dp = [[0] * 2 for i in range(n)]

ans = l[:]

for i in range(k):
    for j in range(n):
        tmp = ans[j] + 0.5
        dp[j][0] = (j+1 - tmp)
        dp[j][1] = (j+1 + tmp)

    ans = [0] * n

    for x in range(n):
        for y in range(n):
            if dp[y][0] <= x+1 <= dp[y][1]:
                ans[x] += 1

else:
    print(*ans)

Submission status: Time Limit Exceeded

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

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

dp = [[0] * 2 for i in range(n)]

ans = l[:]

if k > 10**2:
    k = 100
    
for i in range(k):
    for j in range(n):
        dp[j][0] = (j+1 - ans[j] - 0.5)
        dp[j][1] = (j+1 + ans[j] + 0.5)

    ans = [0] * n

    for x in range(n):
        for y in range(n):
            if dp[y][0] <= x+1 <= dp[y][1]:
                ans[x] += 1

else:
    print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
b = np.zeros(3*n)
b[n:2*n] = A.copy()
flag = False
def update_blightness(b):
    next_b = np.zeros(3*n)
    for i, bi in enumerate(b[n:2*n]):
        add = np.zeros(3*n)
        add[int(n+i-bi):int(n+i+bi+1)] = 1
        next_b += add
        if list(next_b) == list(b):
            flag = True
    return next_b
for _ in range(k):
    b = update_blightness(b)
    if flag:
        break
ans = list(map(str, map(int, b[n:2*n])))
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
K = min(50,K)
B = [0]*N
for _ in range(K):
  for i in range(N):
    a = max(0,i-A[i])
    b = min(N-1,i+A[i])
    B[a] += 1
    if b+1 <= N-1:
      B[b+1] -= 1
  B = np.cumsum(B)
  A=B
  B = [0]*N
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K, *A = map(int, read().split())
B = [0]*N
for _ in range(K):
  for i in range(N):
    a = max(0,i-A[i])
    b = min(N-1,i+A[i])
    B[a] += 1
    if b+1 <= N-1:
      B[b+1] -= 1
 
  B = np.cumsum(B)
  if (A == B).all():
    break
  A=B
  B = [0]*N
print(*A)

Submission status: Time Limit Exceeded

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

def s(n,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 < n - 1:
      b[r+1] -= 1
  for i in range(n-1):
    b[i+1] += b[i]
  return b

for i in range(min(41,K)):
  A = s(N,A)
  
print(*A)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
for _ in range(K):
    if all([A[i] == N for i in range(N)]):
        break
    else:
        B = [sum(abs(x -y) <= A[y] for y in range(N)) for x in range(N)]
        A = B
 
print(' '.join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import add

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class DualSegmentTree:
    def __init__(self, size: int, segfunc, lazy_ide_ele=0):
        self.lazy_ide_ele = lazy_ide_ele
        self.segfunc = segfunc
        self.N0 = 1 << (size - 1).bit_length()
        self.lazy = [self.lazy_ide_ele] * (2 * self.N0)
    
    def gindex(self, left, right):
        L = left + self.N0
        R = right + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1
            R >>= 1
        while L:
            yield L
            L >>= 1
    
    def propagates(self, *ids):
        for i in reversed(ids):
            idx = i - 1
            v = self.lazy[idx]
            if v == self.lazy_ide_ele:
                continue
            self.lazy[2 * idx + 1] = self.segfunc(self.lazy[2 * idx + 1], v)
            self.lazy[2 * idx + 2] = self.segfunc(self.lazy[2 * idx + 2], v)
            self.lazy[idx] = self.lazy_ide_ele
    
    def update(self, left: int, right: int, x):
        L = self.N0 + left
        R = self.N0 + right
        
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R - 1] = self.segfunc(self.lazy[R - 1], x)
            if L & 1:
                self.lazy[L - 1] = self.segfunc(self.lazy[L - 1], x)
                L += 1
            L >>= 1
            R >>= 1
    
    def query(self, k: int):
        self.propagates(*self.gindex(k, k + 1))
        return self.lazy[k + self.N0 - 1]


def solve():
    N, K = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    for _ in range(min(K, 41)):
        dual_seg_tree = DualSegmentTree(N, add)
        for i in range(N):
            left = max(0, i - A[i])
            right = min(N - 1, i + A[i])
            dual_seg_tree.update(left, right + 1, 1)
        for i in range(N):
            A[i] = dual_seg_tree.query(i)
    print(*A)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

for i in range(K):
  newLightPow = [0]*(N+1)
  #print(lightPow)
  for pos in range(1, N+1):
    low = pos - lightPow[pos-1]
    high = pos + lightPow[pos-1]
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    newLightPow[low-1] += 1
    newLightPow[high] -= 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
    
  check = True
  for i in range(0, N):
    if (i > 0):
      newLightPow[i] += newLightPow[i-1]
    if (newLightPow[i] < N):
      check = False
  lightPow = newLightPow
  if (check):
    break

print(*lightPow[:-1])

Submission status: Time Limit Exceeded

Solution code:
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*(N+1)
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        A2[g-1]+=1
        A2[h]-=1
    A[0]=A2[0]
    for j in range(1, N):
        A[j]=A[j-1]+A2[j]
    A2 = [0]*(N+1)
    c = 0
    for p in range(N):
        c+=A[p]
    if c >= N*N:
        break

print(*A)

Submission status: Time Limit Exceeded

Solution code:
# 累積和
import numpy as np


def loop(n, k, A):
    for _ in [0] * k:
        B = np.zeros(n + 1, dtype=np.int64)
        for i in range(n):
            left = max(0, i - A[i])
            right = min(n, i + A[i] + 1)
            B[left] += 1
            B[right] -= 1
        A = np.cumsum(B)[:-1]
        #print(A)
        if np.all(A == n):
            return A
            break

    return A


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    A = np.array(a, dtype=np.int64)
    A = loop(n, k, A)
    print(*A)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
N, K = map(int, input().split())
lightPow = list(map(int, input().split()))
 
for i in range(K):
  newLightPow = [0]*(N+1)
  #print(lightPow)
  for pos in range(1, N+1):
    count = 0
    low = math.ceil(pos-(lightPow[pos-1]+0.5))
    high = math.floor(pos+(lightPow[pos-1]+0.5))
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    newLightPow[low-1] += 1
    newLightPow[high] -= 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
  check = True
  #print(newLightPow)
  for i in range(1, N):
    newLightPow[i] += newLightPow[i-1]
    if (newLightPow[i] < (N-1)):
      check = False
  lightPow = newLightPow
  if (check):
    break

print(*lightPow[:-1])

Submission status: Time Limit Exceeded

Solution code:
import math
N, K = map(int, input().split())
lightPow = list(map(int, input().split()))
 
for i in range(K):
  newLightPow = [0]*(N+1)
  #print(lightPow)
  for pos in range(1, N+1):
    count = 0
    low = math.ceil(pos-(lightPow[pos-1]+0.5))
    high = math.floor(pos+(lightPow[pos-1]+0.5))
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    newLightPow[low-1] += 1
    newLightPow[high] -= 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
  for i in range(1, N+1):
    newLightPow[i] += newLightPow[i-1]
  lightPow = newLightPow
  check = True
  for pow in lightPow:
    if (pow < (N-1)) :
      check = False
    if not (check):
      break
  if (check):
    break
  
print(*lightPow[:-1])

Submission status: Time Limit Exceeded

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

A_list = np.array([0]+list(map(int, input().split())))
#print(A_np)

for j in range(K):
  new_A=np.array([0]*(N+1))
  for i in range(1,N+1):
    #print(A_np)
    mi=i-A_list[i]
    ma=i+A_list[i]
    if mi<0:
      mi=0
    if ma>N:
      ma=N
    new_A[mi:ma+1]+=1
  A_list=new_A
  if sum(A_list[1:N+1])==N*N:
    break
    
for i in range(1,N+1):
  print(A_list[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
num=10**5
for i in range(num):
  [0 for _ in range(num)]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit

num_of_lamps, num_of_operation = map(int, input().split())
intensitys = np.array(list(map(int, input().split())))

coordinates = np.arange(1, len(intensitys) + 1)

@jit
def main(coordinates, intensitys, num_of_lamps, num_of_operation):
    intensity_area_min = []
    intensity_area_max = []
    
    for o in range(num_of_operation):
        intensity_area_min = coordinates - intensitys - 0.5
        intensity_area_max = coordinates + intensitys + 0.5

        # i + 1が自分の座標
        for i in range(num_of_lamps):
            if intensitys[i] < num_of_lamps:
                # 自分より大きい（自分除く）の座標indexのminリストの中から自分の座標より小さいものを探してカウント
                min_count = np.count_nonzero(intensity_area_min[i+1:] <= i + 1)
                # 自分より小さい（自分除く）の座標indexのmaxリストの中から自分の座標より大きいものを探してカウント
                max_count = np.count_nonzero(intensity_area_max[:i] >= i + 1)

                # + 1は自分
                intensitys[i] = min_count + max_count + 1

        if np.all(intensitys >= num_of_lamps):
            break
            
    return intensitys

out = ",".join(map(str, main(coordinates, intensitys, num_of_lamps, num_of_operation)))
print(out.replace(',', ' '))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
c = [0]*N

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

print(" ".join(str(a) for a in A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit

@jit
def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if np.all(num_light == n):
    break
    
print(*num_light)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

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

Submission status: Time Limit Exceeded

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

for i in range(K):
  newLightPow = [0]*N
  #print(lightPow)
  for pos in range(1, N+1):
    count = 0
    low = math.ceil(pos-(lightPow[pos-1]+0.5))
    high = math.floor(pos+(lightPow[pos-1]+0.5))
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    for area in range(low, high+1):
      #print(area)
      newLightPow[area-1] += 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
  lightPow = newLightPow
  check = True
  for pow in lightPow:
    if (pow < (N-1)) :
      check = False
    if not (check):
      break
  if (check):
    break
  
print(*lightPow)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit


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

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

        if A == next_A:
            return A
        A = next_A
    return A


N, K = map(int, input().split())
A = [int(x) for x in input().split()]
print(" ".join([str(x) for x in solve(N, K, A)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if np.all(num_light == n):
    break
    
print(*num_light)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
    a=B[:N]        
  if min(a)==N:
    break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
p=0
while p<K:
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
    a=B[:N]
  p +=1        
  if min(a)==N:
    break
print(*a)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    b = [0 for i in range(n + 1)]
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n, i + a[i] + 1)
        b[l] += 1
        b[r] -= 1
    for i in range(len(b)-1):
        b[i+1] += b[i]
    b = b[:n]
    if a == b:
        break
    else:
        a = b
for i in range(n):
    print(b[i])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
for _ in range(K):
    imos = [0] * (N+1)
    for i in range(N):
        left = max(0, i-A[i])
        right = min(N-1, i+A[i])+1
        imos[left] += 1
        imos[right] += -1

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

    is_all_equal = True
    for i in range(N):
        if A[i] != next_A[i]:
            is_all_equal = False
            break
    if is_all_equal:
        break
    A = next_A
print(" ".join([str(x) for x in A]))

Submission status: Time Limit Exceeded

Solution code:
import math

n,k = map(int,input().split())
lamps = list(map(int,input().split()))
lights = [0 for i in range(n)]

for i in range(k):
  for j in range(n):
    for r in range(max(j-lamps[j], 0), min(j+lamps[j]+1, n)):
      lights[r] += 1
  lamps = lights[:]
  lights = [0 for i in range(n)]
  if i >= math.log2(n):
    lamps = [n for i in range(n)]
    break

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
N, K= map(int,input().split())
A = list(map(int,input().split()))
p=0
while p<K:
  B=[0]*(N+1)
  for i in range(N):
    t = A[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
    A=B[:N]
  p +=1        
  if min(A)==N:
    break
print(*A)

Submission status: Time Limit Exceeded

Solution code:
def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  n = len(a)
  for i in range(n):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < n:
      ret[end+1] -= 1
  for i in range(1,n):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)

Submission status: Time Limit Exceeded

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  for i in range(1,N):
    D[i]+=D[i-1]
  A=D[:-1]
  return A 

for i in range(min(K,42)):
  A=f(A)
print(*A)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

#O(N)
def imos(x):
  global N
  B = np.zeros_like(x)
  for i in range(N):
    p = x[i]
    L = max(i-p, 0)
    R = min(i+p, N-1)
    B[L] += 1
    if R < N-1:
      B[R+1] -= 1
  B = np.cumsum(B)
  return B

for i in range(K):
  if i >= 50:
    break
  A = imos(A)

print(*A)

Submission status: Time Limit Exceeded

Solution code:
def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  for i in range(len(a)):
    start = max(0, i-a[i])
    end = min(n-1, i+a[i])
    ret[start] += 1
    if end+1 < len(a):
      ret[end+1] -= 1
  for i in range(1,len(a)):
    ret[i] += ret[i-1]
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A)

fin = np.array([N] * N)


@njit(cache=True)
def calc_b(a):
    b = np.array([0] * N)
    for i in range(N):
        if a[i] == N:
            b[i] = a[i]
        else:
            l = max(0, i - a[i])
            r = min(N - 1, i + a[i])

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


for k in range(K):
    a = calc_b(a)

    if all(a == fin):
        break

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

Submission status: Time Limit Exceeded

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  A=np.cumsum(D)
  return A 

for i in range(min(K,42)):
  A=list(f(A))  
  
print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
for _ in range(K):
    imos = [0] * (N+1)
    for i in range(N):
        left = max(0, i-A[i])
        right = min(N-1, i+A[i])+1
        imos[left] += 1
        imos[right] += -1

    next_A = [0] * N
    next_A[0] = imos[0]
    for i in range(1, N):
        next_A[i] = next_A[i-1] + imos[i]
    A = next_A

    is_all_max = True
    for i in range(N):
        if A[i] != N:
            is_all_max = False
            break
    if is_all_max:
        break
print(" ".join([str(x) for x in A]))

Submission status: Time Limit Exceeded

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

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

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

print(*a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A)

fin = np.array([N] * N)


@jit(nopython=True)
def calc_b(a):
    b = np.array([0] * N)
    for i in range(N):
        if a[i] == N:
            b[i] = a[i]
        else:
            l = max(0, i - a[i])
            r = min(N - 1, i + a[i])

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


for k in range(K):
    a = calc_b(a)

    if (a == fin).all():
        break

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

Submission status: Time Limit Exceeded

Solution code:
def count_num_light(a):
  ret = [0 for _ in range(len(a))]
  for i in range(len(a)):
    start = max(0, i-a[i])
    end = min(n, i+a[i]+1)
    for j in range(start, end):
      ret[j] += 1
  
  return ret
                  
n, k = map(int, input().split())
a = list(map(int, input().split()))
num_light = count_num_light(a)
 
for i in range(k-1):
  num_light = count_num_light(num_light)
  if sum(num_light) == n**2:
    break
    
print(*num_light)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K= map(int,input().split())
A = list(map(int,input().split()))
p=0
while p<K:
  B=[0]*(N+1)
  for i in range(N):
    B[max(i-A[i],0)] +=1
    B[min(i+A[i]+1,N)] -=1
  A = np.cumsum(B)
  p +=1        
  if min(A[0:N])==N:
    break
print(*A[0:N])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
for _ in range(K):
    imos = [0] * (N+1)
    for i in range(N):
        left = max(0, i-A[i])
        right = min(N-1, i+A[i])+1
        imos[left] += 1
        imos[right] += -1
    next_A = [0] * N
    next_A[0] = imos[0]
    for i in range(1, N):
        next_A[i] = next_A[i-1] + imos[i]
    A = next_A
print(" ".join([str(x) for x in A]))

Submission status: Time Limit Exceeded

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

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    d=A[j]
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  A=np.cumsum(D)
  return A 

for i in range(min(K,42)):
  A=list(f(A))  
  
print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, K= map(int,input().split())
A = list(map(int,input().split()))
p=0
while p<K:
  B=[0]*(N+1)
  for i in range(N):
    l = max(i-A[i],0)
    r = min(i+A[i]+1,N)
    B[l] +=1
    B[r] -=1
  A = np.cumsum(B)
  p +=1        
  if min(A[0:N])==N:
    break
print(*A[0:N])

Submission status: Time Limit Exceeded

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

def f(A):
  D=[0]*(N+1)
  for j in range(N):
    d=A[j]
    mi=max(j-A[j],0)
    ma=min(j+A[j],N-1)
    D[mi]+=1
    D[ma+1]-=1   
  A=np.cumsum(D)
  return A 

for i in range(K):
  D=f(A)
  A=list(D)  
  if A[:-1]==[N]*(N):
    break
print(*A[:-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
light = [[(i+1)-a[i],(i+1)+a[i]] for i in range(n)]
r = []

for i in light:
    r.extend(list(range(i[0],i[1]+1)))

c = Counter(r)

A = [0]*n

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

for _ in range(k-1):
    light = [[(i+1)-A[i],(i+1)+A[i]] for i in range(n)]
    r = []
    for i in light:
        r.extend(list(range(i[0],i[1]+1)))
    c = dict(Counter(r))

    if len(c.keys()) == 1:
        break

    A = [0]*n
    for j in range(1,n+1):
        A[j-1] = c[j]

print(*A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def count_num_light(a):
  ret = np.array([0 for _ in range(len(a))])
  for i in range(len(a)):
    start = max(0, i-a[i])
    ret[start:i+a[i]+1] += 1
  
  return ret
                  
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
num_light = count_num_light(a)

for i in range(k-1):
  num_light = count_num_light(num_light)
  if np.sum(num_light) == n**2:
    break

print(*num_light)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import i8, njit

def main():
    N, K = tuple(int(c) for c in input().split(' '))
    A = [0]
    A.extend(tuple(int(c) for c in input().split(' ')))
    A = np.array(A, dtype=np.int64)
    ret = solve(N, K, A)
    print(' '.join([str(s) for s in ret[1:]]))

@njit(i8[:](i8,i8,i8[:]))
def solve(N, K, A):
    for _ in range(K):
        B= np.zeros(N+1, dtype=np.int64)
        for i in range(1, N+1):
            lower = max(1, i-A[i])
            upper = min(N, i+A[i])
            #print(i, lower, upper)
            B[lower:upper+1] += 1
        A = B
        if np.all(A[1:] == N):
            return A
    return A

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

  for j in range(N - 1):
    B[j + 1] += B[j]
  
  if A == B:
    break
  A = B
  
for b in B:
  print(b, end=" ")

Submission status: Time Limit Exceeded

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

for i in range(K):
  newLightPow = [0]*N
  #print(lightPow)
  for pos in range(1, N+1):
    count = 0
    low = math.ceil(pos-(lightPow[pos-1]+0.5))
    high = math.floor(pos+(lightPow[pos-1]+0.5))
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    for area in range(low, high+1):
      #print(area)
      newLightPow[area-1] += 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
  lightPow = newLightPow
  
print(*lightPow)