Problem:


Score : 500 points

Problem Statement

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

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

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

Find the intensity of each bulb after the K operations.

Constraints

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

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

0 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

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

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

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2 

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

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3 



Sample input:
5 1
1 0 0 1 0


Sample output:
1 2 2 1 2

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    zeros=[0 for i in range(n)]
    if max(a)==0:
        a=[1]*n
        print(*a)
        exit()
    if min(a)==n:
        print(*a)
        exit()

    for i in range(k):
        x=zeros.copy()
        for j in range(n):
            if a[j]==0:
                l=j
                r=min(j+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                #print(r)
                    x[r]+=-1
                #print(x)
            else:
                l=max(0,j-a[j])
                r=min(j+a[j]+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                    #print(r)
                    x[r]+=-1
                #print(x)
        ruiseki=[0]*n
        ruiseki[0]=x[0]
        a[0]=ruiseki[0]
        mina=a[0]
        for i in range(1,n):
            ruiseki[i]=ruiseki[i-1]+x[i]
            a[i]=ruiseki[i]
            if a[i]<mina:
                mina=a[i]
        if mina==n:
            print(*a)
            exit()
        #print(*ruiseki)
    print(*a)
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.insert(0, 0)
B = [0] * (N+1)

def operation():
  global A, B, N
  for i in range(1, N+1):
    left = math.ceil(i - A[i] - 0.5)
    right = math.floor(i + A[i] + 0.5)
    if left < 1:
      left = 1
    if right > N:
      right = N
    for j in range(left, right+1):
      B[j] += 1


operation()

#print(A)
#print(B)

for _ in range(K):
  for i in range(1, N+1):
    if A[i] != B[i]:
      A[i] = B[i]
    B[i] = 0
  operation()
  if A == B:
    ans = [N] * N
    print(ans)
    sys.exit()

print(A[1:])

Submission status: Wrong Answer

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:
    cnt = 1
    while 2 ** (cnt-1) < N:
        cnt += 1
    cnt += 1
    if cnt+1 <= K:
        ans = [N]*N
        print(" ".join(map(str,ans)))
    else:
        old = np.array(A)
        for _ in range(K):
            if min(old) == N:
                break
            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)
                np.maximum(Next[MIN:MAX+1],Next[MIN:MAX+1]+1,out = Next[MIN:MAX+1])
            old = Next
        print(*old)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

for i in range(0,k):
  npb=np.zeros(n, dtype=int)
  for j in range(0,n):
    js=j-npa[j]
    je=j+npa[j]
#    if (js <=0): js=0
#    if (je >=n-1): je=n-1
    npb[js:je+1]+=1

  npa=npb

print (*npa)

Submission status: Wrong Answer

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

b=[a, [0]*n]
next=0
swon=[0]*n

for i in range(k):
  now=i%2
  next=(i+1)%2
  old=next

  for j in range(n):
    swon[j]=b[now][j]-b[old][j]
    b[next][j] = b[now][j] if b[now][j] != 0 else 1
  
  for j in range(n):
    for i in range(swon[j]):
      oneg = j - b[now][j] + i
      opog = j + b[now][j] - i
      if 0 <= oneg < n:
        b[next][oneg] += 1
      if 0 <= opog < n:
        b[next][opog] += 1

for i in range(n-1):
    print(b[next][i], end=" ")
print(b[next][n-1])

Submission status: Wrong Answer

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:
    cnt = 1
    while 2 ** (cnt-1) < N:
        cnt += 1
    cnt += 1
    if cnt+2 <= K:
        ans = [N]*N
        print(" ".join(map(str,ans)))
    else:
        old = np.array(A)
        for _ in range(K):
            if min(old) == N:
                break
            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)
                np.maximum(Next[MIN:MAX+1],Next[MIN:MAX+1]+1,out = Next[MIN:MAX+1])
            old = Next
        print(*old)

Submission status: Wrong Answer

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

for i in range(k + 1):
    a.append([0] * n)
flag = 0

for i in range(k):
    if i == 0:
        for j in range(n):
            for l in range(-a[i][j], a[i][j] + 1):
                if 0 <= j + l < n:
                    a[i + 1][j + l] += 1
    else:
        for j in range(n):
            a[i + 1][j] += a[i][j]
        for j in range(n):
            if a[i][j] - a[i - 1][j] != 0:
                for l in range(1, a[i][j] - a[i - 1][j] + 1):
                    if 0 <= j - a[i - 1][j] - l:
                        a[i + 1][j - a[i - 1][j] - l] += 1
                    if j + a[i - 1][j] + l < n:
                        a[i + 1][j + a[i - 1][j] + l] += 1
    if sum(a[i]) == n ** 2:
        flag = 1
        print(*a[i])
        break

if flag == 0:
    print(a[k])

Submission status: Wrong Answer

Solution code:
import sys

rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n, k = rm()
a = rl()
if n <= k:
    for _ in range(n):
        print(n, end=' ')
        exit()
for _ in range(k):
    li = [0] * n
    for i in range(n):
      s = max(i - a[i], 0)
      e = min(i + a[i], n-1)
      for m in range(s, e+1):
        li[m] += 1
    if a == li:
      break
    a = li
for v in a:
    print(v, end=' ')

Submission status: Wrong Answer

Solution code:
import copy

def get_imos(base, a, k, n):
  min_pos = max(k-a, 0)
  max_pos = min(n-1, a+k)
  base[min_pos] += 1
  base[max_pos] -= 1

def main():
  n, k = map(int, input().split())
  a_list = list(map(int, input().split()))
  base = [0] * n
  for j in range(k):
    for i in range(n):
      get_imos(base, a_list[i], i, n)
    for i in range(1, n):
      base[i] += base[i-1]
    a_list = copy.copy(base)
  print(' '.join(str(x) for x in a_list))
     
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    zeros=[0 for i in range(n)]
    if max(a)==0:
        a=[1]*n
        print(*a)
        exit()

    for i in range(k):
        x=zeros.copy()
        for j in range(n):
            if a[j]==0:
                l=j
                r=min(j+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                #print(r)
                    x[r]+=-1
                #print(x)
            else:
                l=max(0,j-a[j])
                r=min(j+a[j]+1,n)
                #print(l,r)
                x[l]+=1
                if r!=n:
                    #print(r)
                    x[r]+=-1
                #print(x)
        ruiseki=[0]*n
        ruiseki[0]=x[0]
        a[0]=ruiseki[0]
        mina=a[0]
        for i in range(1,n):
            ruiseki[i]=ruiseki[i-1]+x[i]
            a[i]=ruiseki[i]
            if a[i]<mina:
                mina=a[i]
        if mina==n:
            print(*a)
            exit()
        #print(*ruiseki)
    print(*a)
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections

N,K = map(int,input().split())
FA = list(map(int,input().split()))
ANS = [N]*N
sm=[0]*N
la=[0]*N

for i in range(N):
    sm[i] = max(0,i-FA[i]-K+1)
    la[i] = min(N-1,i+FA[i]+K-1)
SM = collections.Counter(sm)
LA = collections.Counter(la)

SM = sorted(SM.items(),reverse=True)
LA = sorted(LA.items())

cnt=0
jdex = 0
for i in reversed(range(N)):
    ANS[i] -= cnt
    if(jdex!= len(SM) and i==SM[jdex][0]):
        cnt += SM[jdex][1]
        jdex += 1

cnt=0
jdex = 0
for i in range(N):
    ANS[i] -= cnt
    if(jdex!= len(LA) and i==LA[jdex][0]):
        cnt += LA[jdex][1]
        jdex += 1


print(*ANS)

Submission status: Wrong Answer

Solution code:
import copy
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
if max(A)==0:
  ans1=[0]*n
  print(' '.join(map(str, ans1)))
  exit()
if k>=n-1:
  ans2=[n]*n
  print(' '.join(map(str, ans2)))
  exit()

for c in range(k):
  B=[0]*len(A)
  for i in range(1,len(A)+1):#1~N
    for j in range(i-A[i-1],i+A[i-1]+1):
      if j>0 and j<=len(A):
        B[j-1]+=1#0~N-1
  A=copy.deepcopy(B)
print(' '.join(map(str, A)))

Submission status: Wrong Answer

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

lst = [0 for i in range(n)]
for j in range(k):
  for t in range(n):
    lst[t]+=1
    for r in range(n):
      if t-(a[t]+0.5)<=r and r<=t+(a[t]+0.5) and t!=r:
        lst[r] = lst[r] + 1 
    
    #print(lst)
  a = lst
  #print(a)
print(a)

Submission status: Wrong Answer

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    key = 15
    nn = n
    while nn > 0:
        key += 1
        nn //= 2
    
    for _ in range(min([key, k])):
        b = [0]*n
        for i in range(n):
            l, r = max([i-a[i], 0]), min([i+a[i], n-1])
            b[l] += 1
            if r != n-1:
                b[r+1] -= 1
        for i in range(n):
            a[i] = 0
            a[i] += b[i]
            if i != 0:
                 a[i] += a[i-1]
    print(*a)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial, log
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):
        B[max(i-A[i], 0)] += 1
        idx = min(i+A[i]+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(log(N)):
        break

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

for k in range(K):
    B = np.zeros(N).astype(int)
    for i in range(N):
        B[max(0, i-A[i]):min(N, i+A[i]+1)] += 1
    A = B

print(A)

Submission status: Wrong Answer

Solution code:
import copy
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [1] * n
for _ in range(k):
    for i in range(n):
        light = 0
        for j in range(n):
            if i < j:
                if (j - a[j] - 0.5) < i:
                    light += 1
            else:
                if (j + a[j] + 0.5) > i:
                    light += 1
        b[i] = light
    a = copy.deepcopy(b)
print(a)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
A = list(map(int, input().split()))
B = [0]*N
for i in range(K):
  for j in range(N):
    for l in range(max(0,j-A[j]),min(j+A[j]+1,N)):
      B[l] = B[l]+1
  ans = B
for i in range(N):
  ans[i] = str(ans[i])
print(" ".join(ans))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def conv(A,N):
    #A(座標iの電灯の強さリスト)からB(座標iを照らしている電灯数)への変換
    B=[0 for n in range(N)]
    for n in range(1,N+1):
        il_min=max(int(n-A[n-1]-0.5)+1,0)
        il_max=min(int(n+A[n-1]+0.5),N)
        for i in range(il_min-1,il_max):
            B[i]+=1
    return B

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

    if K>30:
        A=[N for n in range(N)]
        A[-1]=2*N
    else:
        for k in range(K):
            B=conv(A,N)
            if A==B:
                break
            else:
                A=B
    return " ".join(list(map(str,A)))

if __name__=="__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
from math import log2
def input(): return sys.stdin.readline().strip()

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

    if 30 <= K:
        ans = [N] * N
        print(" ".join(map(str, ans)))
    else:
        for _ in range(K):
            B = [0] * (N + 1)
            for i in range(N):
                head = max(i - A[i], 0)
                tail = min(i + A[i] + 1, N)
                B[head] += 1
                B[tail] -= 1
            A = list(accumulate(B))[:N]
        print(" ".join(map(str, A)))
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

for k in range(K):
    B = np.zeros(N).astype(int)
    for i in range(N):
        print(max(0, i-A[i]), min(N, i+A[i]+1))
        B[max(0, i-A[i]):min(N, i+A[i]+1)] += 1
    A = B

print(A)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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): #これでA[i]ごとにみる
        j = max(0,i-A[i])
        while j<=min(N-1,i+A[i]):
            B[j] = B[j]+1
            j = j+1
        # for j in range(N):#影響を与えるBを+1
        #      B[j] = B[j]+1 if i-A[i]<=j and j<=i+A[i] else B[j]
    A = B
print(B)

Submission status: Wrong Answer

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

import heapq  # heapqライブラリのimport
#heapq.heapify(a)  # リストを優先度付きキューへ
#heapq.heappop(a)  # 最小値の取り出し
    #heapq.heappush(a, -2)
import copy
for unko in range(k):

    denkyu=[]
    heapq.heapify(denkyu)
    cnt=0
    ans=[0]*n
    #print("start",a)
    for i,aa in  enumerate(a):
        if cnt==0:
            ans[i]+=1
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        else:
            while 1:
                tmp=heapq.heappop(denkyu)
                if i<tmp:
                    heapq.heappush(denkyu, tmp)
                    break
                else:
                    cnt-=1
                if cnt==0:
                    break
            
            ans[i]+=cnt+1
            
            if aa>0:
                cnt+=1
                heapq.heappush(denkyu,i+aa+1)
        #print(aa,denkyu)
    #print(unko,ans,a)


    denkyu=[]
    heapq.heapify(denkyu)
    cnt=0
    for ii in  range(n):
        
        i=n-ii-1
        if cnt==0:
            if a[i]>0:
                cnt+=1
                heapq.heappush(denkyu,-1*(i-a[i]-1))
        else:
            while 1:
                tmp=heapq.heappop(denkyu)*(-1)
                if i>tmp:
                    heapq.heappush(denkyu, tmp*(-1))
                    break
                else:
                    cnt-=1
                if cnt==0:
                    break
  
            ans[i]+=cnt
            if a[i]>0:
                cnt+=1
                heapq.heappush(denkyu,(i-a[i]-1)*(-1))
        #print("migi",a[i],denkyu)

    
    if min(a)==n:
        break
    #print(unko,a)


print(" ".join(list(map(str,a))))

Submission status: Wrong Answer

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 > 38:
  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: Wrong Answer

Solution code:
n, k = list(map(lambda x: int(x), input().split(" ")))
 
# only two list object used
blightNess = list(map(lambda x: int(x), input().split(" ")))
cosu = [1] * n
 
def increment(x, blight):
    left = x - blight if x - blight > 0 else 0
    right = x + blight if x + blight <= n - 1 else n - 1
    for i in range(left, right + 1):
        if i != x:
            cosu[i] = cosu[i] + 1
 
def operation(cosu, blightNess):
    cosu = [1] * n
    for i in range(0, n):
        if blightNess[i] != 0:
            increment(i, blightNess[i])
 
    return cosu
    
for i in range(0, k):
    cosu = operation(cosu, blightNess)
    tmp = blightNess
    blightNess = cosu
    cosu = tmp
 
print(" ".join(list(map(lambda x:str(x),blightNess))))

Submission status: Wrong Answer

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

if K > N/2 + 2:
    A = [N]*N
else:
    for _ in range(K):
        if all(e >= N for e in A):
            break
        B = [0] * N
        for i in range(N):
            if A[i] >= 0:
                if (A[i] >= max(N - i, i)):
                    B = list(map(lambda x: x+1, B))
                else:
                    B[i] += 1
                    for j in range(A[i]):
                        if (i - j - 1 >= 0):
                            B[i-j-1] += 1
                        if (i + j + 1 < N):
                            B[i+j+1] += 1
            A = copy.copy(B)

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

import numpy as np

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    
    b=np.cumsum(tab)
    a=b[:]
    
    if time.time()-t1>1.3:
        print(*a)
        exit()
print(*a)

Submission status: Wrong Answer

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
        print(counter)
    for i in range(N):
        P += imos[i]
        A[counter + 1][i] = P
    counter += 1
    if counter == K:
        break
print(" ".join(map(str,A[-1])))

Submission status: Wrong Answer

Solution code:
import collections

N,K = map(int,input().split())
FA = list(map(int,input().split()))
ANS = [N]*N
sm=[0]*N
la=[0]*N

for i in range(N):
    sm[i] = max(0,i-FA[i]-K+1)
    la[i] = min(N-1,i+FA[i]+K-1)
SM = collections.Counter(sm)
LA = collections.Counter(la)

SM = sorted(SM.items(),reverse=True)
LA = sorted(LA.items())

print(SM)
print(LA)


cnt=0
jdex = 0
for i in reversed(range(N)):
    ANS[i] -= cnt
    if(jdex!= len(SM) and i==SM[jdex][0]):
        cnt += SM[jdex][1]
        jdex += 1

cnt=0
jdex = 0
for i in range(N):
    ANS[i] -= cnt
    if(jdex!= len(LA) and i==LA[jdex][0]):
        cnt += LA[jdex][1]
        jdex += 1


print(*ANS)

Submission status: Wrong Answer

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 > 37:
  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)