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:
        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:
N,K = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]

N_count = A.count(N)
N_flag = [False for _ in range(N)]

next_A = [0 for _ in range(N+1)]

if K > 41:
    print(*[N for _ in range(N)])
    exit()
for count in range(K):
    for i in range(N+1): next_A[i] = 0

    for x,a in enumerate(A):
        if a == 0:
            next_A[x] += 1
            next_A[x+1] -= 1
        else:
            next_A[max(x-a,0)] += 1
            next_A[min(x+a+1,N)] -= 1

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

    A = next_A[:N]
    for x,a in enumerate(A):
        if a == N and not N_flag[x]:
            N_flag[x] = True
            N_count += 1
    if N_count == N:
        break
print(count)

Submission status: Wrong Answer

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

if K+sum(A)>=N-1:
    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:
from collections import defaultdict

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

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

def mina(i, rep):
    global n
    if rep == 0:
        return 0
    else:
        return min(2**(rep-1)+i, 2**rep-1, 2**(rep-1)+(n-i-1), n)

lb = 1
rep = 0

da = dict()
for i in range(n):
    if a[i] != 0:
        da[i] = a[i] 

while lb <= 2*n and rep < k:
    db = defaultdict(int)
    for i in da:
        for j in range(i+mina(i, rep)+1, min(i+mina(i, rep)+da[i], n-1)+1):
            db[j] += 1
        for j in range(i-mina(i, rep)-1, max(i-mina(i, rep)-da[i], 0)-1, -1):
            db[j] += 1
    da = db
    lb *= 2
    rep += 1

for i in range(n):
    a[i] = mina(i, rep) + da[i]

print(da)

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

"""
def nextLights(A, Denn):
    Lights = Denn
    i = 1
    for a in A:
        line = np.ones(a*2+1, dtype = int)
        Lights[i-1, n+i-a:n+i+a+1] = line
        i+=1
    Lights = Lights[:, n+1:2*n+1]
    Next_A = np.sum(Lights, axis=0)
    return Next_A
"""

n, k = map(int, input().split())
A = [int(a) for a in input().split()]

#Denn = np.zeros((n, 3*n+2), dtype = int)

if k >= n+1:
    print((str(n)+" ")*n)
else:
    """
    for i in range(k):
        Next_A = nextLights(A, Denn)
        A = A
    """
    L=[str(a) for a in A]
    L=" ".join(L)
    print(L)

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 > 35:
  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:
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):
            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(" ".join(map(str,old)))

Submission status: Wrong Answer

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

N_count = A.count(N)
N_flag = [False for _ in range(N)]

next_A = [0 for _ in range(N+1)]

if K > 40:
    print(*[N for _ in range(N)])
    exit()
for count in range(K):
    for i in range(N+1): next_A[i] = 0

    for x,a in enumerate(A):
        if a == 0:
            next_A[x] += 1
            next_A[x+1] -= 1
        else:
            next_A[max(x-a,0)] += 1
            next_A[min(x+a+1,N)] -= 1

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

    A = next_A[:N]
    for x,a in enumerate(A):
        if a == N and not N_flag[x]:
            N_flag[x] = True
            N_count += 1
    if N_count == N:
        break
print(count)

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 > 30:
  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:
import math

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:
    break
else:
  print(A[1:])

ans = [N]* N
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

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

for k in range(K):
    B = [0 for _ in range(N)]
    for i in range(N):
        left = max(i-A[i], 0)
        right = min(i+A[i], N-1)
        for j in range(left, right+1):
            B[j] += 1
    A = copy.deepcopy(B)
print(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 > 25:
  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:
# -*- 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 > 20:
  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:
import numpy as np

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

for j in range(0,n):
    js=j-((k-1)+npa[j])
    je=j+((k-1)+npa[j])
    if (js <=0): js=0
    if (je >=n-1): je=n-1
    print (js,je)
    npb[js:je+1]+=1

print (*npb)

Submission status: Wrong Answer

Solution code:
from sys import stdin

n, k = [int(x) for x in stdin.readline().rstrip().split()]
intense_counters = [0]
dd = [int(x) for x in stdin.readline().rstrip().split()]
intense_counters.extend(dd)

max_intense = False
additional = 0
if k >= n-1:
    print(" ".join([str(n)]*n))
else:
    for times in range(k):
        counter = 0
        new_intense_counters = [0] * (n+1)
        add_all = 0
        for i, intense in enumerate(intense_counters):
            if i == 0:
                continue
            intense += additional

            if intense == n-1:
                counter += 1
                add_all += 1
            else:
                min = i - intense
                if min < 1:
                    min = 1
                max = i + intense
                if max > n:
                    max = n

                if min == 1 and max == n:
                    add_all += 1
                else:
                    for lighted_position in range(min, max+1):
                        new_intense_counters[lighted_position] += 1
        if counter == n:
            max_intense = True
            break
        intense_counters = new_intense_counters
        additional = add_all

    if max_intense:
        print(" ".join(list(map(str, [n]*n))))
    else:
        print(" ".join(list(map(str, intense_counters[1:]))))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    flag = 0
    for _ in range(K):
        imos = [0]*(N + 1)
        if flag == N:
            print([N]*(N))
            return
        for i in range(N):
            imos[max(0,i  - A[i])] += 1
            imos[min(N,i + 1 + A[i])] -= 1
        for j in range(N):
            imos[j+1] += imos[j]
            flag += 1 if imos[j] == N else 0
        A = imos[:N].copy()
    print(*A,sep=" ")
    return 

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

for x in range(k-1):
  b = [0]*n
  
  for x in range(n-1):
    
    if a[x] != 0:
    
      add = [1]*(a[x]*2+1)
      b = [x + y for (x, y) in zip(a, b)]
    
  a = [x + y for (x, y) in zip(a, b)]

print(a)

Submission status: Wrong Answer

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


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



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


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

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

mod = 10**9+7


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


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

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


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

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

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

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


Al=[0]*(N+1)

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




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

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

#print(B)
#print(res)

Submission status: Wrong Answer

Solution code:
import collections

n, K = map(int, input().split())
a = [int(i) for i in input().split()]

for k in range(K):
    change_list = []
    for i in range(n):
        if k > 0:
            a[i] = counter[i+1]
        change_list.extend([j for j in range(1,n+1) if i-a[i]+0.5 < j < i+a[i]+1.5])
    counter = collections.Counter(change_list)
    # for m in range(n):
    #     a[m] = counter[m+1]

ans_list = [str(c) for c in a]
ans=' '.join(ans_list)
print(ans)