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 = [0]+list(map(int, input().split()))
A_np=np.array(A_list)
#print(A_np)

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

Submission status: Time Limit Exceeded

Solution code:
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

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

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

#A = [0 for i in range(N)]
B = [0 for i in range(N)]

# print(A)
for _ in range(K):
    B = [0 for i in range(N)]
    for i in range(N):
        tmp = A[i]
        B[max(i-tmp, 0)] += 1
        idx = min(i+tmp+1, N)
        if idx != N:
            B[idx] -= 1
    # print(B)
    for i in range(N-1):
        B[i+1] += B[i]
    # print(B)
    A = B.copy()
    if _ > 2 * int(sqrt(N)):
        break

L = " ".join([str(x) for x in A])
print(L)

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]*N
    for x in range(N):
        for b in range(-A[x], A[x]+1):
            if x+b >= 0 and x+b < N:
                B[x+b] += 1
    A = B

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
import numpy as np
N,K = map(int,input().split())
A = list(map(int,input().split()))
if N == 1:
    print(1)
else:
    old = np.array(A)
    if K <= 5:
        for _ in range(K):
            Next = np.zeros(N,dtype = np.int64)
            for i in range(N):
                a = old[i]
                MIN = max(0,i-a)
                MAX = min(N-1,i+a)
                Next[MIN:MAX+1] += 1
            old = Next
        old = list(old)
        print(*old)
    else:
        for _ in range(5):
            Next = np.zeros(N,dtype = np.int64)
            for i in range(N):
                a = old[i]
                MIN = max(0,i-a)
                MAX = min(N-1,i+a)
                Next[MIN:MAX+1] += 1
            old = Next
        for _ in range(K-5):
            Next = np.zeros(N,dtype = np.int64)
            vmax = max(old)
            for i in range(N):
                p = 1
                if i - vmax >= 0:
                    p += vmax
                    if old[i-vmax] != vmax:
                        p -= 1
                else:
                    p += i
                if i + vmax <= N-1:
                    p += vmax
                    if old[i+vmax] != vmax:
                        p -= 1
                else:
                    p += (N-1-i)
                Next[i] = p
            old = Next
        print(*old)

Submission status: Time Limit Exceeded

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

for i in range(k):
    ans=[0]*(n)
    for j in range(n):
        l=max(0,j-a[j])
        r=j+1+a[j]
        ans[l]+=1
        if r<n:
            ans[r]-=1
    for z in range(n-1):
        ans[z+1]+=ans[z]
    a=ans
    if ans[0]==n and ans[n-1]==0:
        print(" ".join(list(map(str,ans))))
        sys.exit()
print(" ".join(list(map(str,ans))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

# = int(input())
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
length = len(A)
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

if K >= N:
    L=[str(length) for a in range(N)]
    L=" ".join(L)
    print(L)
    exit()
else:
    for i in range(K):
        count = 0
        zero = np.array([0]*N)
        for j in range(N//2):
            if A[j] >= length-(j+1):
                zero += 1
            else:
                count += 1
                if j + A[j] + 1 >= length:
                    zero[j:] += 1
                else:
                    zero[j:A[j]+j+1] += 1
                if j - A[j] - 1 < 0:
                    zero[:j] += 1
                else:
                    zero[j-A[j]:j] += 1
        for j in range(N//2, N):
            if A[j] >= j:
                zero += 1
            else:
                count += 1
                if j + A[j] + 1 >= length:
                    zero[j:] += 1
                else:
                    zero[j:A[j]+j+1] += 1
                if j - A[j] - 1 < 0:
                    zero[:j] += 1
                else:
                    zero[j-A[j]:j] += 1
        if count == 0:
            break
        else:
            A = zero

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,K = IL()
A = IL()
if K > 500:
  A = [N for i in range(N)]
  print(*A)
  exit()
  
while True:
  if K == 0:
    break
  SEGLEN = 18
  seg = [0 for i in range(2**(SEGLEN+1))]
  for i in range(N):
    l = max(0,i-A[i])
    r = min(N-1,i+A[i])
    l += 2**SEGLEN
    r += 2**SEGLEN+1
    while l < r:
      if l%2 == 1:
        seg[l] += 1
      if r%2 == 1:
        seg[r-1] += 1
      l = -(-l//2)
      r = r//2
  A = []
  MIN = INF
  for i in range(N):
    i += 2**SEGLEN
    ans = 0
    while i:
      ans += seg[i]
      i //= 2
    A.append(ans)
    MIN = min(MIN,ans)
  K -= 1
  if MIN == N:
    break
  
print(*A)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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


for _ in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]

print(*arr)

Submission status: Time Limit Exceeded

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

# 一度照らされると二度目以降は確実に照らされるはず。
for i in range(K):
    # j番目の電球を操作
    B = np.array([0] * N)
    if list(set(A)) == [N]:
        break
    for j in range(N):
        if A[j] == N:
            B[j] = N
            continue
        maxA = int(j + A[j] + 0.5)
        minA = math.ceil(j - A[j] - 0.5)

        for k in range(max(0, minA), min(N, maxA + 1)):
            B[k] += 1
    A = B.copy()

for i in range(N):
    if i != (N - 1):
        print(A[i], end=" ")
    else:
        print(A[i])

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(v) for v in input().strip().split(" ")]
A = [int(v) for v in input().strip().split(" ")]

for i in range(K):
    new_A = [0] * N
    for x in range(N):
        for k in range(max(x - A[x], 0), min(x + A[x] + 1, N)):
            new_A[k] += 1
    A = new_A
    full_flag = True
    for x in range(N):
        if A[x] != N:
            full_flag = False
    if full_flag:
        break
    # print("run on %s" % i)

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

Submission status: Time Limit Exceeded

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

def manupi(A):
  return [sum([A[nx] >= abs(nx- n) for nx in range(N)]) for n in range(N)]

for _ in range(K):
  A = manupi(A)
print(" ".join(map(str,A)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k = map(int, input().split())
a = list(map(int, input().split()))
a = np.asarray(a, dtype=int)
if k<n:
    for i in range(k):
        b = np.zeros(n, dtype=int)
        for j in range(n):
            if a[j]>0:
                mi = j-a[j]
                ma = j+a[j]
                if mi<0:
                    mi = 0
                if ma>=n:
                    ma = n-1
                for k in range(mi,ma+1):
                    b[k]+=1
            else:
                b[j]+=1
        a = b
        if np.mean(a)==n:
            break
else:
    for i in range(n):
        a[i] = n
print(*a)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N,K = LI()
    a = LI()

    for _ in range(K):
        x = [0] * N
        for i in range(N):
            s = i - a[i]
            if s < 0: s = 0
            x[s] += 1
            t = i + a[i] + 1
            if t < N:
                x[t] -= 1
        a = []
        cnt = 0
        for i in range(N):
            cnt += x[i]
            a.append(cnt)

    print(*a,sep=' ')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

temp=A
max_pow=0
first_look=0

for i in range(K):
  max_pow=max(A)
  temp=[0]*len(A)

  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: Time Limit Exceeded

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

for j in range(k):
    s = [0] * (n + 1)
    for i in range(n):
        if i - a[i] >= 0:
            s[i - a[i]] += 1
        else:
            s[0] += 1
        if i + a[i] + 1 < n + 1:
            s[i + a[i] + 1] -= 1
        else:
            s[n] -= 1
            
    s_ = [0] * (n + 1)
    s_[0] = s[0]
    for i in range(n):
        s_[i + 1] = s_[i] + s[i + 1]
        
    a = s_
    
print(*s_[:n])

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().rstrip().split(" "))
A = [list(map(int,input().rstrip().split(" ")))]
imos = [0 for i in range(N + 1)]
P = 0
flag = True
counter = 0
while flag:
    A.append([0 for i in range(N)])
    P = 0
    for i in range(N+1):
        imos[i] = 0
    for i in range(N):
        imos[max(0,i - A[counter][i])] += 1
        imos[min(N,i + A[counter][i] + 1)] -= 1
    if imos[0] == N and imos[N] == -1 * N:
        flag = False
    for i in range(N):
        P += imos[i]
        A[counter + 1][i] = P
    counter += 1
    if counter == K:
        break
print(" ".join(list(map(str,A[-1]))))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,K = IL()
A = IL()
if K > 1000:
  A = [N for i in range(N)]
  print(*A)
  exit()
  
while True:
  if K == 0:
    break
  SEGLEN = 18
  seg = [0 for i in range(2**(SEGLEN+1))]
  for i in range(N):
    l = max(0,i-A[i])
    r = min(N-1,i+A[i])
    l += 2**SEGLEN
    r += 2**SEGLEN+1
    while l < r:
      if l%2 == 1:
        seg[l] += 1
      if r%2 == 1:
        seg[r-1] += 1
      l = -(-l//2)
      r = r//2
  A = []
  MIN = INF
  for i in range(N):
    i += 2**SEGLEN
    ans = 0
    while i:
      ans += seg[i]
      i //= 2
    A.append(ans)
    MIN = min(MIN,ans)
  K -= 1
  if MIN == N:
    break
  
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

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

    count = min(K-1, N//2+1)
    for _ in range(count):
        B_list = cal_B(B_list)

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

Submission status: Time Limit Exceeded

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]
a=[str(s) for s in a]
a=" ".join(a)
print(a)

Submission status: Time Limit Exceeded

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

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

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

ans = A

for _ in range(K):
    A_ = ans
    ans = [0] * N
    for i in range(N):
        acc = A_[i]
        for j in range(max(0, i - acc), min(N - 1, i + acc) + 1):
            ans[j] += 1
            ans[j] = min(ans[j], N)
    A_ = ans

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#import numba

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

#@numba.jit
rireki = []
def answer(N,K,A):
    for count in range(K):
        newA = [list(itertools.chain.from_iterable([[i2 + 1 for i2 in range(int(i + 1 - v - 0.5),int(i + 1 + v + 0.5))] for i,v in enumerate(A)])).count(i + 1) for i,v in enumerate(A)]
        if newA in rireki:
            amari = K % count
            A = rireki[amari - 1]
            break
        rireki.append(newA)
        if newA == A:
            break
        A = newA
        if len(A) == A.count(len(A)):
            #print("OK")
            break
    return A

A = answer(N,K,A)
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split())) 
for kk in range(k):
  b = []
  for i,j in enumerate(a):
    il, ir = i, i
    sl, sr = 1, 1
    bi = 1
    while il != 0:
      il -= 1
      if a[il] >= sl:
        bi += 1
      sl += 1
    while ir != n-1:
      ir += 1
      if a[ir] >= sr:
        bi += 1
      sr += 1
    b.append(bi)
  a = b
print(*b)

Submission status: Time Limit Exceeded

Solution code:
from random import randint

# print('input >>')
N, K = map(int,(input().split()))
As = list(map(int,(input().split())))

# N, K = 1000, 100
# As = [0] * 1000
# As[0] = 1

# まずはナイーブにやる(TLEでもういいよ。。。)
for t in range(K):
    baseAs = [1] * len(As)
    for i in range(len(As)):
        d = As[i]
        if d == 1000:
            continue
        for j in range(d):
            if i-j-1 >= 0:
                baseAs[i-j-1] += 1
            if i+j+1 < len(As):
                baseAs[i+j+1] += 1
    As = baseAs[:]
    if all([A == N for A in As]):
        break

# print('-----output-----')
for A in As:
    print(A, end=' ')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def Lamps():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))

    for i in range(K):
        next_A_list = np.zeros(len(A_list), dtype = int)

        for denkyu_num in range(len(A_list)):
            for j in range(A_list[denkyu_num] + 1):
                if denkyu_num + j < len(A_list):
                    next_A_list[denkyu_num + j] += 1
                if denkyu_num - j >= 0 and j != 0:
                    next_A_list[denkyu_num - j] += 1
            #print(j, next_A_list)

        A_list = next_A_list
        #print()

    print(' '.join(map(str, list(A_list))))

Lamps()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,K=map(int,input().split())
a=input().split()
A=[int(b) for b in a]
A=np.array(A)
suuji=0
for k in range(K):
    a = [1 for _ in range(N)]
    for n in range(N):
        a=np.array(a)
        number=A[n]
        plus=n+number
        minus=n-number
        if minus<0:
            minus=0
        a[minus:n]+=1
        a[n+1:plus+1]+=1
    A=a
    if sum(A)==N**2:
        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())))
z = [0 for _ in range(n)]

for i in range(k):
    next_a = np.array(z)
    for j in range(n):
        next_a[max(j - a[j], 0):min(j + a[j] + 1, n)] += 1
    a = next_a
print(' '.join(list(map(str, a.tolist()))))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
sf=[[0,0] for i in range(n)]#sfは区間の最初と最後を表す最初は+0.5最後は-0.5
seen=[list(range(n)) for i in range(n)]
nmax=list(range(n))
#初期の時点で各々の座標において入っている電球の数
count=0
while count<k:
    count+=1
    cnmax=nmax[:]
    if len(nmax)==0:
        break
    for i in cnmax:
        if a[i] == n:
            nmax.remove(i)
        else:
            sf[i][0] = i - a[i]
            sf[i][1] = i + a[i]
            if sf[i][0] < 0:
                sf[i][0] = 0
            if sf[i][1] >= n:
                sf[i][1] = n - 1
            if count==1:
                for j in range(sf[i][0], sf[i][1] + 1):
                    seen[j].remove(i)
    for i in nmax:
        if not count==1:
            cseen=seen[i][:]
            for j in cseen:
                if sf[j][0]<=i<=sf[j][1]:
                    seen[i].remove(j)
    for i in nmax:
        a[i]=n-len(seen[i])
for i in range(n):
    if i==n-1:
        print(a[i])
    else:
        print(a[i], end=" ")

Submission status: Time Limit Exceeded

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

a_tmp = [0] * n
a_range = []*n
#print(a_tmp)

for i in range(k):
    for x in range(n):
        # まずは一つ目が照らしている電球を考える
        # 範囲は式通り
        left = math.ceil(x - a_array[x] - 0.5)
        if left < 0:
            left = 0
        right  = math.floor(x + a_array[x] + 0.5)
        if right > n - 1:
            right = n -1
        #a_tmp = [a_tmp[i]+1 if (i>=left and i<right+1) else a_tmp[i] for i in range(0, n)]
        
        a_tmp2 = [0] * n
        a_insert = [1] * (right+1 - left)
        #print(a_insert)
        
        #a_tmp2[left:right-1] = a_insert
        a_tmp2[left:right] = a_insert
        #print(a_tmp2)
        
        a_tmp = [x + y for (x, y) in zip(a_tmp2,a_tmp)]

        #for j in range(left, right+1):
            #a_tmp[j] += 1
        
        #print(a_tmp)
    a_array = a_tmp
    a_tmp = [0]*n

ans = " ".join(map(str, a_array))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

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

@njit(cache=True)
def calc(A, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-A[i]))
        right = int(min(N-1, i+A[i]))
        b[left:right+1] +=1
 
    A = b.copy()
    if step < K:
        step += 1
        return calc(A, step)
    else:
        return A
ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))

Submission status: Time Limit Exceeded

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

class segtree:
    x_unit=0 # 要素として入れられる最大値
    def __init__(self,N):
        self.n=(1<<len(bin(N-1)[2:]))
        self.x=[self.x_unit]*(2*self.n)

    def build(self, seq):
        for i,j in enumerate(seq, start=self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = 0
            # セグ木トーナメント表の左右を比較
            # 例えばn=8の時、seq[4]はx[12]に、seq[5]はx[13]に入っている
            # さらにx[14]とx[15]の間に来るのはx[7]、x[12]とx[13]の間に来るのはx[6]

    def fold(self,l,r): # 区間[l, r)値に+1 
        l+=self.n
        r+=self.n-1
        while l<r:
            if l%2==1: # lが奇数
                self.x[l]+=1
                l+=1 # 偶数に調節
            if r%2==0: # rが偶数
                self.x[r]+=1
                r-=1 # 開区間なので1個前は奇数番目の要素
            l //= 2
            r //= 2
        if l==r:
            self.x[l]+=1
        #print(self.x)
    def get(self,i): # seq[i]に対する値を取得 
        i+=self.n
        ret=self.x[i]
        while i>1:
            i //= 2
            ret+=self.x[i]
        return ret

for z in range(min(k,100)):
    seq=[0]*n
    q=[(max(0, i-a[i]), min(n,i+a[i]+1)) for i in range(n)]
    seg=segtree(n)
    seg.build(seq)
    for i in range(n):
        l,r=q[i]
        seg.fold(l,r)
    ans=[]
    for i in range(n):
        ans.append(seg.get(i))
    a=ans+[]
    if all([i==n for i in a]):
        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):
    tmp = A[:]
    A = [0 for _ in range(N)]
    for j in range(N):
        a = tmp[j]
        for k in range(max(0, j-a),min(N, j+a+1)):
            A[k] += 1
print(*A)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

def main():
    N,K = LI()[:]
    A = LI()
    #print(N,K)
    #print(A)

    for k in range(K):
        B = [0]*N
        for i, a in enumerate(A):
            #print(i, a)
            if a == 0:
                B[i] += 1
            else:
                # i-(a+0.5) ~ i+(a+0.5)
                # i: 整数、a: ＋整数　なので +0.5 は切り捨てられる。
                #　影響範囲は、 i-a ~ i+a
                for p in range(i-a,i+a+1):
                    #print("p:",p)
                    if p >=0 and p < N:
                        B[p] += 1
                #print(B)
        if k < K-1:
            A = B

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
if N%2 == 0:
    b = N//2
else:
    b = (N//2) +2
if N==1:
    print(1)
    exit()
if K >= b:
    for i in range(N-1):
        print(N,end=" ")
    print(N)
    exit()

for k in range(K):
    nextgen = [0]*N
    for i in range(N):
        # print("i=",i)
        a = A[i]
        start = i-a
        if i-a <0:
            start = 0
        end = i+a+1
        if i+a+1 <=N-1:
            nextgen[end] += -1
            end = N-1
        # print(start,end)
        nextgen[start] += 1
        # print(nextgen)
    dp = 0
    for i in range(N):
        dp += nextgen[i]
        A[i] = dp
s = ' '.join([str(i) for i in A])
print(s)