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: Runtime Error

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

for i in range(k):
  b=[0]*n
  cnt=0
  for j in range(n):
    if a[j]>=max(n-j,j)
    cnt+=1
  if cnt==n:
    for i in j in range(n):
      a[j]=(k-i)*n
    break
  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: Runtime Error

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


def change(arr):
  newAs = [0] * n
  for i, a in enumerate(arr):
    for t in range(max(i - a, 0), min(i + a + 1, n)):
      newAs[t] += 1
  return newAs


for temp in min(range(k),10**4)):
  As = change(As)
print(' '.join(map(str, As)))

Submission status: Runtime Error

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

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

for j in range(k):
    b = [0]*n
    for i in range(n):
        if i-a[i]>0:
            start = i-a[i]
        else:
            start = 0
        if i+a[i]>n:
            end = n-1
        else:
            end = i+a[i]
        for l in range(start,end+1):
            b[l] += 1
    a = b


print(*a)

Submission status: Runtime Error

Solution code:
import numpy as np


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

loop_cnt = 0
while loop_cnt < k:
    if all(a >= n):
        a = np.array([n] * n)
        break

    new_a = np.zeros(n, dtype=np.int64)

    for j in range(n):
        new_a[max(0, j - a[j]): min(n, j + a[j] + 1)] += 1

    a = new_a
    loop_cnt += 1

a = k * (n - 1)

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

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
i_list = input().split()
d_list = [0]*n

for x in range(k-1):
  
  for x in range(n-1):
    d_list[x-(i_list[x]-1):x+(i_list[x]-1)] += 1
  
  i_list +=  d_list
  
print(i_list)

Submission status: Runtime Error

Solution code:
a, v = map(int, input().split())
b, w = map(int, input().split())
k = int(input())
x = a + v * k
y = b + w * k
if a == b:
    print('YES')
elif (a < b and v < w) or a < b:
    print("NO")
else:
    print('YES')

Submission status: Runtime Error

Solution code:
# import numpy as np
import sys
import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


def sp_xnxn(n=0):
    """
    args:
        int n: a number of lows to read
    example
        input   1
        retrun  [1]

        input   123
        return  [1,2,3]

        input   123
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        return [int(k) for k in xsxs()]
    else:
        return [[int(k) for k in xsxs()] for _ in range(n)]


def xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
    example:
        input   AA
        retrun  AA

        input   A BBB CC
        return  ["A","BBB","CC"]

        input   A BB CCC
                D
        return  [["A","BBB","CC"],
                ["D"]]
    """
    if n == 0:
        temp = list(input().split())
        if len(temp) == 1:
            return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        return [list(input().split()) for _ in range(n)]


def sp_xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
        example:
            input   A
            retrun  ["A"]

            input   ABC
            return  ["A","B","C"]

            input   ABC
                    D
            return  [["A","B","C"],
                    ["D"]]
    """
    if n == 0:
        return [s for s in xsxs()]
    else:
        return [[s for s in xsxs()] for _ in range(n)]


n, k = xnxn()
a = xnxn()
a = [1] + a
for _ in range(k):
    # tmp = copy.copy(a)
    tmp = []
    for i in range(1, n + 1):
        idx = []
        c = 0
        for k in range(1, n + 1):
            if k - tmp[k] - 0.5 < i < k + tmp[k] + 0.5:
                c += 1
        a[i] = c

for i in a[1:]:
    print(i, end=" ")

Submission status: Runtime Error

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

bef = copy.copy(A)
aft = [0 for _ in range(n)]

for k in range(K):
    for i in range(n):
        a = bef[i]
        aft[max(0, i-a):min(n-1, i+a)+1] = map(lambda x: x+1, aft[max(0, i-a):min(n-1, i+a)+1])
    #     aft[max(0, i-a):min(n-1, i+a)] +=1
#         print(aft[max(0, i-a):min(n-1, i+a)+1])
    if bef == aft:
        break
    bef = copy.copy(aft)
    aft = [0 for _ in range(n)]
print(*bef)

Submission status: Runtime Error

Solution code:
l1= input().split(' ')
n= l1[0]
k= int(l1[1])

start= input().split(' ')

def f(ar, n):
	new= []
	for _ in range(n):
		new.append(0)
	for index in range(n):
		d= int(start[index])
		if index-d<0:
			if index+d>len(ar)-1:
				for k in range(0, n):
					new[k]+=1
			else:
				for k in range(0, index+d+1):
					new[k]+=1
		elif index+d>len(ar)-1:
			for k in range(index-d, n):
				new[k]+=1
		else:
			for k in range(index-d, index+d+1):
				new[k]+=1
	return new


for _ in range(0,k):
	start= f(start, n)
print(*start, sep=' ')

Submission status: Runtime Error

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


for i in range(k):
  B=[0 for i in range(n)]
  for j in range(n):
    d=A[j]
    mi=j-d
    ma=j+d
    if mi=<0:
      mi=0
    if ma>=n:
      ma=n-1
    while mi<=ma:
      B[mi]=B[mi]+1
      mi=mi+1
  A=B
for i in range(int(len(A))):
  print(A[i],end="")
  if i!=int(len(A)):
    print(" ",end="")

Submission status: Runtime Error

Solution code:
for t in range(K):
    temp=A
    for j in range(N):
        ans[j]+=1
        for s in range(1,temp[j]+1):
            if  j+s<=N-1:
                ans[j+s]+=1
            if 0<=j-s:
                ans[j-s]+=1   
    if t!=K-1:
        A=ans
        ans=list(0 for i in range(N))
   
       
print(ans)

Submission status: Runtime Error

Solution code:
def lightup_one_tern(N, A):
    A_new = [0]*N
    for i in range(N):
        A_new[i] += 1
        for d in range(1, A[i]+1):
            if((i+d)<=N):
                A[i+d] += 1
            if((i-d)>=0):
                A[i-d] += 1
    return A_new

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

for k in range(K):
    A = lightup_one_tern(N, A)
return A

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n<=k:
    print(' '.join([n]*n))
    exit()
for _ in range(k):
    ans=[0]*n
    for i in range(n):
        count=0
        for j in range(n):
            if abs(i-j)<=int(a[j]):
                count += 1
        ans[i]=str(count)
    a=ans
print(' '.join(a))

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

def main():
    n, k = list(map(int,sys.stdin.readline().split()))
    A = list(map(int,sys.stdin.readline().split()))
    for i in range(k):
        next_A = [0] * (n + i)
        for x in range(n):
            if A[x] == 0:
                next_A[x] += 1
            else:
                if x - A[x] > 0:
                    start = (x - A[x])
                else: start = 0 
                if x + A[x] < n:
                    end = x + A[x]
                else: end = n
                for tmp in range(start, end+1):
                    next_A[tmp] += 1
        A = deepcopy(next_A)
    print(' '.join([str(number) for number in A[:n]]))
    return 0

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = [int(v) for v in input().split(" ")]
start = time.time()
step = np.arange(len(A_arr))
def Luminate(A_arr, i):
  isLuminated = np.abs(step - i) < np.array(A_arr)+1
  return isLuminated
def get_Intensity(A_arr):
  return [np.sum(Luminate(A_arr, i)) for i in range(len(A_arr))]
Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity)

print(" ".join([str(v) for v in Intensity]))

Submission status: Runtime Error

Solution code:
import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
B = np.zeros(N, dtype="int")
coordinate = np.arange(1, N+1)


for _ in range(K):
    A = [(A >= np.abs(coordinate - coordinate[i])).sum() for i in range(N)]

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

Submission status: Runtime Error

Solution code:
def spots(lista, K, N):
  if K == 0:
    return lista
  else:
    newlista = spots(lista, K- 1, N)
    ans = [0]* N
    i = 0
    for item in newlista:
      ans[i] += 1
      for j in range(1, item + 1):
        if i + j < N:
          ans[i+ j] += 1
        if i - j >= 0:
          ans[i- j] += 1
      i += 1
      
    return ans

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

if(N <= K):
  for i in range(N):
    print(N, "", end = "")

else:
  for item in spots(lista, K, N):
    print(item, "", end = "")
  print()

Submission status: Runtime Error

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

for k in range(K):
    for i in range(N):
        for a in range(A[i] + 1):
            B[i + a]+= 1
            if i-a >= 0:
                B[i - a] += 1
    for i in range(N):
        if k != K-1:
            A[i] = B[i]
        else:
            print(A[i], "", end = '')

Submission status: Runtime Error

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

for k in range(K):
    for i in range(N):
        for a in range(A[i] + 1):
            B[i + a]+= 1
            if i-a >= 0:
                B[i - a] += 1
    for i in range(N):
        if k != K-1:
            A[i] = B[i]
        else:
            print(A[i], " ", end = '')

Submission status: Runtime Error

Solution code:
def spots(lista, K, N):
  if K == 0:
    return lista
  else:
    newlista = spots(lista, K- 1, N)
    ans = [0]* N
    i = 0
    for item in newlista:
      ans[i] += 1
      for j in range(1, item + 1):
        if i + j < N:
          ans[i+ j] += 1
        if i - j >= 0:
          ans[i- j] += 1
      i += 1
      
    return ans

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

for item in spots(lista, K, N):
  print(item, "", end = "")
print()

Submission status: Runtime Error

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


for i in range(k):
  B=[0 for i in range(n)]
  for j in range(n):

    d=A[j]
    mi=j-d
    ma=j+d
    if mi<0:
      mi=0
    if ma>n:
      ma=n-1
    while mi<=ma:
      B[mi]=B[mi]+1
      mi=mi+1
  A=B
for i in range(int(len(A))):
  print(A[i],end="")
  if i!=int(len(A)):
    print(" ",end="")

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }


int main(){
    LL n, k;
    cin >> n >> k;
    vector<LL> a(n);
    for(LL i = 0; i < n; ++i){
        cin >> a[i];
    }

    for(LL i = 0; i < k; ++i){
        vector<LL> diff(n+1);
        for(LL j = 0; j < n; ++j){
            LL left = max(0LL, j - a[j]);
            LL right = min(n, 1 + j + a[j]);
            diff[left] += 1;
            diff[right] -= 1;
        }
        LL cur = 0;
        for(LL i = 0; i < n; ++i){
            cur += diff[i];
            a[i] = cur;
        }
        bool flag = true;
        for(LL i = 0; i < n; ++i){
            if(a[i] != n) flag = false;
        }
        if(flag) break;
    }

    for(LL i = 0; i < n; ++i){
        if(i+1 == n){
            cout << a[i] << endl;
        }else{
            cout << a[i] << " ";
        }
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=gcd(a,b,c)
print(ans)