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 copy

N, K = [int(x) for x in input().strip().split(" ")]
A = [int(x) for x in input().strip().split(" ")]

for _ in range(K):
    an = [0 for _ in range(N)]
    for i, a in enumerate(A):
        min_ = i - a
        max_ = i + a
        for j in range(min_, max_+1):
            if not (0 <= j < N):
                continue
            an[j] += 1
    A = an
print(" ".join([str(a) for a in A]))

Submission status: Time Limit Exceeded

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

l= [str(a) for a in l]
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()))
current = a[:]
for _ in range(k):
    next = np.array([0]*n)
    for j, v in enumerate(current):
        c = np.array([1 if j-v <= k <= j+v else 0 for k in range(n)])
        next += c
    current = next
print(*next)

Submission status: Time Limit Exceeded

Solution code:
class DualSegTree():
    def __init__(self,n):
        self.n=n
        self.data=[0]*n*2
    def propagate(self,i):
        if i>=self.n*2:return
        data=self.data
        c,j=0,i
        while j:
            j>>=1
            c+=1
        for j in range(c-1,0,-1):
            j=i>>j
            data[j+j]+=data[j]
            data[j-~j]+=data[j]
            data[j]=0
    def update(self,l,r,x):
        data=self.data
        l+=self.n
        r+=self.n
        self.propagate(l)
        self.propagate(r)
        while l<r:
            if l&1:
                data[l]+=x
                l+=1
            if r&1:
                r-=1
                data[r]+=x
            l>>=1
            r>>=1
    def get(self,i):
        i+=self.n
        self.propagate(i)
        return self.data[i]
def main():
    n,k,*a=map(int,open(0).read().split())
    seg=DualSegTree(n)
    for i,b in enumerate(a,n):
        seg.data[i]=b
    for _ in range(k):
        d=DualSegTree(n)
        m=10**18
        for i in range(n):
            t=seg.get(i)
            if t<m:m=t
            d.update(max(0,i-t),min(i-~t,n),1)
        seg=d
        if m==n:break
    print(*[seg.get(i)for i in range(n)])
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(k):
    if a == [n] * n:
        break
    else:
        a2 = [0] * (n + 1)
        for j in range(n):
            temp = a[j]
            a2[max(j - temp, 0)] += 1
            a2[min(j + temp + 1, n)] -= 1
        a3 = [0]
        for j in range(n):
            a3.append(a3[-1] + a2[j])
        a = a3[1:]
for i in range(n):
    print(a[i], end = " ")
print()

Submission status: Time Limit Exceeded

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

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):
    next_A = [0] * N
    for i in range(N):
        for j in range(max(0, i-A[i]), min(N-1, i+A[i])+1):
            next_A[j] += 1
    A = next_A
print(" ".join([str(x) for x in A]))

Submission status: Time Limit Exceeded

Solution code:
#import sys
#input = sys.stdin.readline
from itertools import accumulate
def main():
    N, K = map( int, input().split())
    A = list( map( int, input().split()))
    for i in range(K):
        B = [0]*(N+1)
        for j in range(N):
            d = A[j]
            x = j-d
            y = j+d
            if x < 0:
                B[0] += 1
            else:
                B[x] += 1
            if N-1 < y:
                B[N] -= 1
            else:
                B[y+1] -= 1
        A = list( accumulate(B))
        check = True
        for j in range(N):
            if A[j] < N:
                check = False
        if check:
            break
    print(" ".join( map(str, A[:-1])))
            
                
        
if __name__ == '__main__':
    main()

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())))
for _ in [0]*k:
  new_A = np.array([0]*n)
  for i in range(n):
    left = i - A[i]
    right = i + A[i] + 1
    if left < 0:
      new_A[:right] += 1
      if right >= n:
        new_A += 1
    else:
      if right >= n:
        new_A[left:] += 1
      else:
        new_A[left:right] += 1
  A = new_A
   
for a in A:
  print(a, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(k):
        tmp = [0] * n
        for i in range(n):
            for j in range(max(0, i - a[i]), min(n, i + a[i] + 1)):
                tmp[j] += 1
        if a == tmp:
            break
        a = tmp
    print(*a)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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 j in range(n):
    for m in range(j-a[j],j+a[j]+1):
      if 0<=m<=n-1:
        b[m]=b[m]+1
  a=b
for i in a:
  print(i,end=' ')

Submission status: Time Limit Exceeded

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


for k in range(K):
    illumi = [0] * N
    for i in range(N):
        l = A[i]
        for j in range(max(0, i - l), min(N, i + l + 1)):
            illumi[j] += 1

    for i in range(N):
        A[i] = illumi[i]

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

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0 for _ in range(n)]
"""
座標xに光の強さdの電球→[x-d, x+d] てらす
強さ0でもそれには適用.
"""
for _ in range(k):
	b = [0 for _ in range(n)]
	alln = 0
	for i in range(n):
		if a[i] == n:
			alln += 1
		for j in range(max(i-a[i], 0), min(i+a[i]+1, n)):
			b[j] += 1
	if alln == n:
		break
	a = b[:]
print(*b)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def func(A):
    aA = [0]*(2*N+10)
    for i, a in enu(A):
        st = max(0, 2*i-2*a-1)
        en = min(2*N, 2*i+2*a+1)
        aA[st] += 1
        aA[en] -= 1

    for i in range(2*N):
        aA[i+1] += aA[i]

    res = [val for i, val in enu(aA) if i%2==0]
    res = res[:N]
    return res

for _ in range(K):
    A = func(A)

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())))

for i in range(k):
    if 2**i>=n:
        ans = [n]*n
        break
    ans = np.zeros(n,int)
    for j in range(n):
        left = max(j-a[j],0)
        right = min(j+a[j]+1,n)
        ans[left:right] += 1
    
    a = ans.copy()
    
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

n, k, *aaa = map(int, sys.stdin.buffer.read().split())

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

    aaa = list(accumulate(bbb))
    aaa.pop()

    if all(a == n for a in aaa):
        break

print(*aaa)

Submission status: Time Limit Exceeded

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

def func(ls):
    buf = [0] * N

    for i in range(N):
        d = ls[i]

        a = max(0, i - d)
        b = min(N - 1, i + d)

        for j in range(a, b + 1):
            buf[j] += 1
    
    return buf

for i in range(K):
    A = func(A)

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

Submission status: Time Limit Exceeded

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


for k in range(K):
    illumi = [0] * N
    for i in range(N):
        l = A[i]
        for j in range(i - l, i + l + 1):
            if(j >= 0 and j < N):
                illumi[j] += 1

    for i in range(N):
        A[i] = illumi[i]

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

Submission status: Time Limit Exceeded

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

D = [0]*(N+1)
for k in range(K):
  for i in range(N):
    D[i] = 0
  for i in range(N):
    D[max(0, i-A[i])] += 1
    D[min(N, i+A[i]+1)] -= 1
  a = 0
  up = False
  for i in range(N):
    a += D[i]
    if a!=A[i]:
      up = True
      A[i] = a
  if not up:
    break

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


@njit('i8[:](i8,i8,i8[:])', cache=True)
def func(n, k, A):
    for _ in range(k):
        B = np.zeros(n + 1, np.int64)
        for i, a in enumerate(A):
            B[max(0, i - a)] += 1
            B[min(i + a + 1, n)] -= 1
        A = B.cumsum()[:-1]
        if np.all(A == n):
            break
    return A


def main():
    N, K = map(int, readline().split())
    A = np.array(readline().split(), np.int64)
    ans = func(N, K, A)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(a):
        b = [0]*(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(n):
            b[i+1] += b[i]
        return b[:n]
    n,k = LI()
    a = LI()
    while k:
        if sum(a) == n**2:
            break
        a = f(a)
        k -= 1
    print(*a)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from itertools import accumulate
n, k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(min(41, k)):
  _As = [0]*(n+1)
  for j in range(n):
    l = max(0, j - As[j])
    r = min(n - 1, j + As[j])
    _As[l] += 1
    _As[r+1] -= 1
  As = list(accumulate(_As))[:-1]
print(' '.join([str(A) for A in As]))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
C=[n for _ in range(n)]

while k!=0:
    B=[0 for _ in range(n+1)]
    for i,j in enumerate(A):
        B[max(0,i-j)] +=1
        B[min(n,i+j+1)] -=1
    for i in range(1,n):
        B[i] +=B[i-1]
    A=B[:n]
    k -=1
    if A==C:break
print(*A)

Submission status: Accepted

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

while k!=0:
    B=[0 for _ in range(n+1)]
    for i,j in enumerate(A):
        B[max(0,i-j)] +=1
        B[min(n,i+j+1)] -=1
    for i in range(1,n):
        B[i] +=B[i-1]
    A=B[:n]
    k -=1
    if sum(A)==n**2:break
print(*A)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
for _ in range(K):
    count_list = [0] * N
    for i, v in enumerate(A_list):
        count_list[i - v if i - v > 0 else 0] += 1
        if i + v + 1 < N:
            count_list[i + v + 1] -= 1
    temp = 0
    flag = True
    for i in range(len(A_list)):
        temp += count_list[i]
        if temp != N:
            flag = False
        A_list[i] = temp
    if flag:
        break

print(*A_list)

Submission status: Accepted

Solution code:
n, k, *a = map(int, open(0).read().split())

for _ in range(k):
    b = [0] * -~n
    for i in range(len(a)):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]

    if all(x == n for x in b[:n]):
        print(*b[:n])
        exit()
    a = b
print(*a[:n])

Submission status: Accepted

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

for _ in range(min(K, 50)):
    lamp = [0 for i in range(N + 1)]
    for i in range(N):
        lamp[max(0, i - A[i])] += 1
        lamp[min(N, i + A[i] + 1)] -= 1

    for i in range(1, N + 1):
        lamp[i] += lamp[i - 1]
    A = lamp

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

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()

from itertools import accumulate

for _ in range(min(K,41)):
    B = [0]*(N+1)
    for i in range(N):
        a = A[i]
        B[max(i-a,0)] += 1
        B[min(N,i+a+1)] -= 1
    C = list(accumulate(B))
    A = C

print(*[A[i] for i in range(N)])

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()

from itertools import accumulate

for _ in range(min(K,100)):
    B = [0]*(N+1)
    for i in range(N):
        a = A[i]
        B[max(i-a,0)] += 1
        B[min(N,i+a+1)] -= 1
    C = list(accumulate(B))
    A = C

print(*[A[i] for i in range(N)])

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
def f(b):
    rt=[0]*-~n
    for i in range(n):
        d=b[i]
        rt[max(0,i-d)]+=1
        rt[min(n,i+d+1)]+=-1
    for i in range(n-1):
        rt[i+1]+=rt[i]
    return rt[:-1]

for i in range(k):
    a=f(a)
    if sum(a)==n**2:
        break
print(*a)

Submission status: Accepted

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

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


@njit(i8[:](i8, i8, i8[:]), cache=True)
def solve(n, k, arr):
    for i in range(min(k, 50)):
        tmp_arr = np.zeros(n + 1, np.int64)
        for i, power in enumerate(arr):
            tmp_arr[max(0, i - power)] += 1
            tmp_arr[min(n, i + power + 1)] -= 1
        arr = np.cumsum(tmp_arr)[:-1]
    return arr


print(*solve(n, k, arr))

Submission status: Accepted

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

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


@njit(i8[:](i8, i8, i8[:]), cache=True)
def solve(n, k, arr):
    for i in range(min(k, 50)):
        tmp_arr = np.zeros(n + 2, np.int64)
        for i, power in enumerate(arr):
            tmp_arr[max(0, i - power + 1)] += 1
            tmp_arr[min(n + 1, i + power + 2)] -= 1
        arr = np.cumsum(tmp_arr)[1:-1]
    return arr


print(*solve(n, k, arr))

Submission status: Accepted

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

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


@njit(i8[:](i8, i8, i8[:]))
def solve(n, k, arr):
    for i in range(min(k, 50)):
        tmp_arr = np.zeros(n + 2, np.int64)
        for i, power in enumerate(arr):
            tmp_arr[max(0, i - power + 1)] += 1
            tmp_arr[min(n + 1, i + power + 2)] -= 1
        arr = np.cumsum(tmp_arr)[1:-1]
    return arr


print(*solve(n, k, arr))

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

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


@njit
def solve(n, k, arr):
    for i in range(min(k, 50)):
        tmp_arr = np.zeros(n + 2, np.int64)
        for i, power in enumerate(arr):
            tmp_arr[max(0, i - power + 1)] += 1
            tmp_arr[min(n + 1, i + power + 2)] -= 1
        arr = np.cumsum(tmp_arr)[1:-1]
    return arr


print(*solve(n, k, arr))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


show_flg=False
show_flg=True

ans=0

n,k=LI()
a=LI()

def f(b):
    rt=[0]*-~n
    for i in range(n):
        d=b[i]
        rt[max(0,i-d)]+=1
        rt[min(n,i+d+1)]+=-1
    for i in range(n-1):
        rt[i+1]+=rt[i]
    return rt[:-1]

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

print(*a)

Submission status: Accepted

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

N, K = mapint()
As = list(mapint())
from itertools import accumulate

for _ in range(K):
    lamps = [0]*N
    for i, a in enumerate(As):
        lamps[max(0, i-a)] += 1
        if i+a+1<=N-1:
            lamps[i+a+1] -= 1
    As = list(accumulate(lamps))
    if sum(As)==N**2:
        break
print(*As)

Submission status: Accepted

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

def calc_imos(arr):
    imos = [0] * (N + 1)
    for i, a in enumerate(arr):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        imos[l] += 1
        imos[r + 1] -= 1
    new_arr = list(accumulate(imos))[:-1]
    return new_arr


for k in range(K):
    A = calc_imos(A)
    if all([a == N for a in A]):
        print(*([N] * N), sep=' ')
        exit()

print(*A, sep=' ')

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
now = inpl()
for _ in range(k):
    pre = now[::]
    cnt = [0] * (n+1)
    for i in range(n):
        l = max(0, i - pre[i])
        r = min(n, i + pre[i] + 1)
        cnt[l] += 1
        cnt[r] -= 1
    # print(cnt)
    now = [0] * n
    now[0] = cnt[0]
    for i in range(1,n):
        now[i] = now[i-1] + cnt[i]
    if min(now) == n:
        break
print(*now)

Submission status: Accepted

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

for _ in range(K):
    imos = [0] * (N+1)
    for i,a in enumerate(A):
        l = max(0, i-a)
        r = min(N, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    for i in range(N):
        imos[i+1] += imos[i]
    imos.pop()
    A = imos
    if all(a==N for a in A): break
print(*A)

Submission status: Accepted

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

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

for _ in range(min(100,k)):
    imos = [0]*(n+1)
    for i,a in enumerate(al):
        l = max(0,i-a)
        r = min(n,i+a+1)
        imos[l] += 1
        imos[r] -= 1
    new_al = []
    curr_val = 0
    for im in imos[:-1]:
        curr_val += im
        new_al.append(curr_val)
    al = new_al[:]

print(*al)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,K = MI()
A = LI()

from itertools import accumulate

for _ in range(min(K,100)):
    B = [0]*(N+1)
    for i in range(N):
        a = A[i]
        B[max(i-a,0)] += 1
        B[min(N,i+a+1)] -= 1
    C = list(accumulate(B))
    A = C

print(*[A[i] for i in range(N)])

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(k):
  B = [0]*(n+1)
  for i, a in enumerate(A):
    B[max(i-a, 0)] += 1
    B[min(i+a+1, n)] -= 1
  A = list(accumulate(B))[:-1]
  if min(A) == n:
    break
print(*A)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,K=map(int,input().split())

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


for _ in range(K):
    ans=[0]*len(A)
    start=[0]*len(A)
    end=[0]*len(A)
    
    for index,item in enumerate(A):
        start[max(0,index-item)]+=1
        end[min(len(end)-1,index+item)]+=1
    
    #print(start)
    #print(end)
    
    temp=0
    for i in range(len(ans)):
        temp+=start[i]
        ans[i]=temp
        temp-=end[i]
    
    if A==ans:
        break
    else:
        A=ans[:]

print(*ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(min(k,41)):
  b=[0]*(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(n-1):
    b[i+1]+=b[i]
  a=b[:n]
print(*a)

Submission status: Accepted

Solution code:
# 問題文の意味がわからんコンテスト
# 0の場合も自分自身を照らす、っての気づくところからやっと読解
# Kを5000兆回やったあとはすべての要素がNになっとる この収束はわりと早いらしい
n, k = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(min(k, 100)):
    b = [0] * (n + 1)
    for i in range(n):
        b[max(0, i - a[i])] += 1
        b[min(n, i + a[i] + 1)] -= 1
    for i in range(n):
        b[i + 1] += b[i]
    a = b[:n]
print(" ".join(list(map(str, a))))

Submission status: Accepted

Solution code:
import sys
 
import numba as nb
import numpy as np
 
input = sys.stdin.readline
 
 
@nb.njit("i8[:](i8,i8,i8[:])", cache=True)
def solve(N, K, A):
    for _ in range(min(41, K)):
        A_cumsum = np.zeros(shape=N, dtype=np.int64)
        for i in range(N):
            A_cumsum[max(0, i - A[i])] += 1
            b = i + A[i] + 1
            if N - 1 < b:
                pass
            else:
                A_cumsum[b] -= 1
        A = np.cumsum(A_cumsum)
    return A
 
 
def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)
 
    ans = solve(N, K, A)
 
    print(" ".join(map(str, ans)))
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

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

x = X[:] + [0]
for _ in range(K):
    if all(v == N for v in x[:-1]):
        break

    new = [0] * (N + 1)
    for i in range(N):
        new[max(0, i - x[i])] += 1
        new[min(N, i + x[i] + 1)] -= 1

    for i in range(N):
        new[i + 1] += new[i]
    x = new[:]

print(*x[:-1])

Submission status: Accepted

Solution code:
from itertools import accumulate

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

def calc_imos(arr):
  imos=[0]*(N+1)
  for i,a in enumerate(arr):
    l=max(0,i-a) #照らす範囲の左側インデックス、0が最小
    r=min(N-1,i+a) #照らす範囲右側インデックス,arrの長さ-1=Nが最大
    imos[l]+=1
    imos[r+1]-=1
  imos=list(accumulate(imos))
  return imos[:-1]

for k in range(min(50,K)):
  A=calc_imos(A)
print(*A,sep=" ")

Submission status: Accepted

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

print(*a)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
for k in range(min(50, K)):
    B = [0]*N
    for i in range(N):
        B[max(0, i-A[i])] += 1
        r = i+A[i]+1
        if r < N:
            B[r] -= 1
    A = list(accumulate(B))
print(*A)

Submission status: Accepted

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


@njit(i8[:](i8, i8, i8[:]), cache=True)
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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


@jit(i8[:](i8, i8, i8[:]), nopython=True, cache=True)
def myfunc(n, k, A):
    for _ in range(k):
        l = np.zeros((n + 1,), dtype=np.int64)
        for i, a in enumerate(A[:-1]):
            l[max(0, i - a)] += 1
            l[min(n, i + a + 1)] -= 1
        A = np.cumsum(l)
        if np.all(A[:-1] == n):
            break
    return A


def main():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    A = np.append(A, 0)
    print(*myfunc(n, k, A)[:-1])


if __name__ == "__main__":
    main()