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:
// #include <bits/stdc++.h>
#include <iostream>  // cin, cout, string
#include <algorithm> // sort, min/max, upper/lower_bound, transform, count/copy_if
#include <vector>
#include <utility> // pair, swap
#include <functional>
#include <iomanip> // setprecision
#include <map>
#include <set> // multiset
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <stack>
#include <queue> // priority_queue
#include <deque>
#include <bitset>
#include <array>
#include <list>
#include <forward_list>
#include <complex>
#include <ratio>
#include <cassert>
#include <numeric> // accumulate, itoa
#include <random>  // mt19937
#include <iterator>
#include <chrono>
#include <cstring>

using namespace std;

// #define int long long

using i64 = int64_t;
using ll = long long;
using ld = long double;

template <typename T>
using vec = vector<T>;
template <typename T>
using mat = vec<vec<T>>;
template <typename T>
using dic = unordered_map<string, T>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>; // dijkstra
// template<typename T, typename U> using P = pair<T, U>;
// template<typename... Args> using func = function<Args...>;
// template<typename T> using pq = priority_queue<T>;

using pii = pair<int, int>;
using ppi = pair<pii, int>;
using pip = pair<int, pii>;
using ppp = pair<pii, pii>;

using vi = vec<int>;
using mi = mat<int>; // Graph
using vp = vec<pii>;

constexpr int IINF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
// constexpr int INF = sizeof(int) == sizeof(long long) ? LINF : IINF;
constexpr long long MOD = 1e9 + 7;

#define _overload(_1, _2, _3, name, ...) name
#define _rep1(i, a, b) for (int i = (a), _##i = (b); i < _##i; ++i)
#define _rep2(i, n) _rep1(i, 0, n)
#define _rep3(n) _rep2(i, n)
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2, _rep3)(__VA_ARGS__)
#define _rrep1(i, a, b) for (int i = (b)-1, _##i = (a); i >= _##i; --i)
#define _rrep2(i, n) _rrep1(i, 0, n)
#define _rrep3(n) _rrep2(i, n)
#define rrep(...) _overload(__VA_ARGS__, _rrep1, _rrep2, _rrep3)(__VA_ARGS__)

#define each(i, a) for (auto &&i : a)
#define each2(i, a) for (const auto &i : a)

#define pb push_back
// emplace_back(*) == push_back(constructor(*))
#define eb emplace_back
#define pob pop_back
#define pf push_front
#define pof pop_front

#define np next_permutation
#define pp prev_permutation

// make_pair(A, B) == pair<T, U>(A, B)
#define mp make_pair
// mt(...) == tie(...)
#define mt make_tuple

#define ft first
#define sd second

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)(a).size()
#define rev(a) reverse(all(a))
#define rs(a, l) (a).resize(l)

#define upper(s) transform(all(s), (s).begin(), topper)
#define lower(s) transform(all(s), (s).begin(), tolower)

#define sum(a) accumulate(all(a), 0)
#define elif else if
#define unless(a) if (!(a))
#define qt(a) #a

#define endl '\n'
#define dec(n) fixed << setprecision(n)
#define zfl(n) setfill(‘0’) << setw(n)

template <typename T = int, T l = 0, T r = (T)MOD>
auto rnd = bind(uniform_int_distribution<T>(l, r), mt19937(chrono::steady_clock::now().time_since_epoch().count()));

template <typename T>
inline constexpr T gcd(T a, T b)
{
    if (a == 0 || b == 0)
        return 0;
    while (b)
    {
        a = a % b;
        swap(a, b);
    }
    return a;
}
template <typename T>
inline constexpr T extgcd2(T a, T b, T &x, T &y)
{
    x = 1;
    y = 0;
    while (b)
    {
        T t = a / b;
        a -= t * b;
        swap(a, b);
        x -= t * y;
        swap(x, y);
    }
    return a;
}
template <typename T>
inline constexpr T lcm(T a, T b) { return a / gcd(a, b) * b; }

template <typename T>
inline constexpr bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T>
inline constexpr bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

template <typename A, typename B>
istream &operator>>(istream &is, pair<A, B> &p)
{
    is >> p.first;
    is >> p.second;
    return is;
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    os << p.first << " " << p.second;
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (auto &&x : v)
        is >> x;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    for (int i = 0; i < (int)v.size(); ++i)
        cout << v[i] << (i + 1 != (int)v.size() ? " " : "");
    return os;
}

#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg>
void __f(const char *name, const Arg &arg)
{
    cerr << name << " : " << arg << endl;
}
template <typename Arg, typename... Args>
void __f(const char *names, const Arg &arg, const Args &... args)
{
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " : " << arg << " | ";
    __f(comma + 1, args...);
}

inline auto yes(const bool &c) { return c ? "yes" : "no"; }
inline auto Yes(const bool &c) { return c ? "Yes" : "No"; }
inline auto YES(const bool &c) { return c ? "YES" : "NO"; }
inline auto Possible(const bool &c) { return c ? "Possible" : "Impossible"; }
inline auto POSSIBLE(const bool &c) { return c ? "POSSIBLE" : "IMPOSSIBLE"; }

constexpr int lim = 100007; // 10^5+7
int n, k;
vec<int> a;
vec<int> b;
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    a.resize(n);
    b.resize(n);
    rep(n) cin >>
        a.at(i);

    rep(k)
    {
        rep(j, n)
        {
            b.at(j) = 0;
        }
        rep(j, n)
        {
            b.at(max(0, j - a.at(j)))++;
            if (a.at(j) + j + 1 < n)
            {
                // cout << a.at(j) + j + 1 << endl;
                b.at(a.at(j) + j + 1)--;
            }
        }

        rep(j, n - 1)
        {
            b.at(j + 1) += b.at(j);
        }
        int count = 0;
        rep(j, n)
        {
            if (b.at(j) == n)
                count++;
            a.at(j) = b.at(j);
        }
        if (count == n)
            break;
    }
    rep(n) cout << a.at(i) << " ";
    cout << endl;
    return 0;
    cout << "A" << endl;
}

Submission status: Runtime Error

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

for i in range(K):
  new_A_beta = []
  new_A_beta.clear()
  for j in range(N):
    from_num = (j+1) - A[j] -0.5
    to_num = (j+1) + A[j] + 0.5
    for k in range(N):
      if from_num <= (k+1) <= to_num:
        new_A_beta.append(k+1)
    new_A =[]
    new_A.clear()
    for l in range(N):
      new_A.append(new_A_beta.count(l+1))
  if all(elem == N for elem in new_A)
  	print(*new_A)
    exit()
  A.clear()
  for m in new_A:
    A.append(m)
    
print(*new_A)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
ans = [0 for i in range(n)]

for j in range(k):
  ls = [0 for i in range(n)]
  rs = [0 for i in range(n)]
  
  for i in range(n):
    l = max(i - a[i], 0)
    r = min(i + a[i], n-1) + 1
    ls[l] += 1
    if r < n:
      rs[r] += 1

  for i in range(1, n):
    ls[i] += ls[i-1]
    rs[i] += rs[i-1]

  for i in range(n):
    ans[i] = ls[i] - rs[i]
  
  if len(set(ans)) == 1 and ans[0] == n:
    break

  a = ans
  
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

import numpy as np
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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


def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(1,N):
        f = i - A[i]
        t = i + A[i]
        for j in range(max(1, f), min(N, t)):
            B[j] += 1
    
    A = B

for _ in range(1, K):
    proc()

print(" ".join(A))

Submission status: Runtime Error

Solution code:

import numpy as np
def resolve():

    def solve(N, K, A):
        for _ in range(K):
            imos_table = np.zeros(N + 1, np.int64)
            for i, a in enumerate(A):
                # 配列の個数を超えないように注意
                imos_table[max(i - a, 0)] += 1
                imos_table[min(i + a + 1, N)] -= 1
            A = np.cumsum(imos_table)[:-1]
            if np.all(A == N):
                print(*A)
                return
        else:
            print(*A)

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

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#いもす法で解いてみる
#いもす法とは

import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
imosutable=[0]*n*2

for m in range(0,k):
    maxed=0
    for i in range(0,n):
        d=a[i]
        imosutable[max(0,i-d)]+=1
        imosutable[i+d+1]-=1
    for i in range(1,n):
        imosutable[i]+=imosutable[i-1]
        if imosutable[i]==n:
            maxed+=1   

    if maxed==n:
        answer=imosutable[0:n]
        print(' '.join(map(str,a)))
        exit()

    a=copy.copy(imosutable)
    imosutable=[0]*n*2

answer=a[0:n]
for s in answer[0:n-1]:
    print (str(s)+" ",end="")
print(answer[n-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
from numba import njit
import numpy as np

def resolve():
    @njit('i8,i8,i8[::1]',cache=True)
    def solve(N, K, A):
        for _ in range(K):
            imos_table = np.zeros(N + 1, np.int64)
            for i, a in enumerate(A):
                # 配列の個数を超えないように注意
                imos_table[max(i - a, 0)] += 1
                imos_table[min(i + a + 1, N)] -= 1
            A = np.cumsum(imos_table)[:-1]
            if np.all(A == N):
                print(*A)
                return
        else:
            print(*A)

    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())), np.int64)
    solve(N, K, A)
        
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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


def proc():
    B = [0 for _ in range(N)]

    for i in 1 to N:
        f = i - A[i]
        t = i + A[i]
        for j in max(1, f) to min(N, t):
            B[j] += 1
    
    A = B

for _ in 1 to K:
    proc()

print(" ".join(A))

Submission status: Runtime Error

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 41)):
    b = [0]*(n+1)
    for j in range(n):
        b[max(j-a[j], 0)] +=1
        if j+a[j] <n:
            b[j+a[j]+1] -=1
    for j in range(1,n):
        b[j] += b[j-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
from numba import jit
import numpy as np
@jit
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from numba import njit
import numpy as np

@njit
def resolve():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#いもす法で解いてみる
#いもす法とは

import copy
n,k=map(int,input().split())
a=list(map(int,input().split()))
imosutable=[0]*n*2

for m in range(0,k):
    maxed=0
    for i in range(0,n):
        d=a[i]
        imosutable[max(0,i-d)]+=1
        imosutable[i+d+1]-=1
    for i in range(1,n):
        imosutable[i]+=imosutable[i-1]
        if imosutable[i]==n:
            maxed+=1   

    if maxed==n:
        answer=imosutable[0:n]
        print(' '.join(map(str,a)))
        exit()

    a=copy.copy(imosutable)
    imosutable=[0]*n*2


answer=a[0:n]
print(' '.join(map(str,answer)))

Submission status: Runtime Error

Solution code:
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 42)):
    b = [0]*(n+1)
    for i in range(n):
        b[max(i-a[i], 0)] +=1
        if i+a[i] <n:
            b[i+a[i]+1] -=1
    for i in range(1,n):
        b[i] += b[i-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
from numba import njit
import numpy as np
@njit
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
from numba import njit
import numpy as np
@njit(cache=True)
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
from numba import njit
import numpy as np
@njit('i8,i8,i8[::1]',cache=True)
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import numpy as np

N,k = map(int,input().split())
l = [int(a) for a in input().split()]
m = [N] * N
l_st = [0] * (N+1)
for _ in range(k):
    counter += 1
    print(counter)
    a = l_st
    for i,x in enumerate(l):
        a[max(0,i-x)] += 1
        a[min(i+x+1,N)] -= 1
    a_l = np.cumsum(np.array(a))[:-1].tolist()
    if a_l == m:
        break
    else:
        l = a_l
print(' '.join(map(str, a_l)))

Submission status: Runtime Error

Solution code:
import math
n, k = map(int, input().split())
array = list(map(int, input().split()))
Array = [0]*n
def plusone(n):
    return n + 1

for j in range(min(k, int(math.log2(n))):
    for i in range(n):
        ai = array[i]
        Array[max(i-ai, 0):min(i+ai+1,n+1)] = map(plusone, Array[max(i-ai, 0):min(i+ai+1,n+1)])
        if j == k - 1:
            answer = Array
    array = Array
    Array = [0] * n

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

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
Ai = input().split()
Bi = [int(i) for i in Ai]



for n in range(15,K):
    li = [0 for i in range(N)]
    for i,x in enumerate(Bi):
        li[i] += 1
        for l in range(1,x+1):
            if i - l >= 0:
                li[i-l] += 1
            if i + l <= N - 1:
                li[i+l] += 1
    Bi = li
for i in li:
    print(i)

Submission status: Runtime Error

Solution code:
# ac
import numpy as np
from numba import njit
# imos法
@nijt
def update(a):
    n = len(a)
    b = np.zeros_like(a)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n - 1, i + x)  # lampの上限（右側）
        b[l] += 1              # 以下imos法
        if r + 1 < n:          # r+1はx=nの時（最後のサイクル）r+1=nでindexの指定に失敗するから弾く（indexは0~n-1）
            b[r + 1] -= 1
    b = np.cumsum(b)           # bの要素の累積和（フィボナッチ数列みたいな）（imos法の締め）
    return b


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

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する

Submission status: Runtime Error

Solution code:
#import math
import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal

#N=int(input())
N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())


num=np.zeros(N+1)

for i in range(K):
    n=np.zeros(N,dtype='int')
    for m in range(41):
        l=max(0,m-A[m])
        r=min(N,m+A[m])

        n[l:r+1]+=1
    #    print(l,r)

    A=n
    if A.min() == N:
        for k in range(N):
            print(N)
        exit()

for i in range(N):
    print(n[i])

Submission status: Runtime Error

Solution code:
import math

def plus(x):
    return x+1

n,k=map(int,input().split())
A=list(map(int,input().split()))
m=min(min(50,k))
for j in range(m):
    B=[0]*n
    for i in range(n):
        B=B[0:max(0,i-A[i])]+list(map(plus,B[max(0,i-A[i]):min(n,i+A[i]+1)]))+B[min(n,i+A[i]+1):n]
    A=B.copy()

for i in range(n):
    B[i]=str(B[i])

print(' '.join(B))

Submission status: Runtime Error

Solution code:
# ac
import numpy as np
# imos法
def update(a):
    n = len(a)
    b = np.zeros_like(a)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n, i + x)      # lampの上限（右側）
        b[l] += 1              # imos法
        if r  < n + 1:
            b[r] -= 1
    b = np.cumsum(b)           # bの要素の総和（imos法の締め）
    return b

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

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する

Submission status: Runtime Error

Solution code:
import numpy as np

n,k = map(int,input().split())
l = [int(a) for a in input().split()]
l_t = np.array([0] * n)
a = l_t
m = np.array([N] * N)
for _ in range(k):
    for i,x in enumerate(l):
        if i <= x and  N-i-1 <= x:
            X = [1] * N
        elif i <= x:
            X = [1] * (i+1+x) + [0] * (N-i-x-1)
        elif N-i-1 <= x:
            X = [0] * (i-x) + [1] * (x+N-i)   
        else:
            X = [0] * (i-x) + [1] * (2*x + 1) + [0] * (N-x-i-1)
        a += np.array(X)
    if a == m:
        break
    else:
        l = a
        a = l_t
print(a)

Submission status: Runtime Error

Solution code:
import numpy as np

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

for _ in range(K):
    f = np.zeros(N, dtype=np.int)
    for i, e in enumerate(A):
        sp = range(max(0, i - e), min(N, i + e + 1))
        f += np.array([1 if j in sp else 0 for j in range(N)])
    if A == f:
        break
    A = f

print(*A)

Submission status: Runtime Error

Solution code:
import math
n, k = map(int, input().split())
array = list(map(int, input().split()))
Array = [0]*n
def plusone(n):
    return n + 1

for j in range(min(k, math.log2(n))):
    for i in range(n):
        ai = array[i]
        Array[max(i-ai, 0):min(i+ai+1,n+1)] = map(plusone, Array[max(i-ai, 0):min(i+ai+1,n+1)])
        if j == k - 1:
            answer = Array
    array = Array
    Array = [0] * n

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

def imos(A):
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        a = max(0, i-x)
        b= min(i+x, N-1)
        B[a] += 1
        if b+1 <= N-1:
            B[b+1] -= 1
    B = np.cumsum(B)

for i in range(K):
    if i >= 50:
        break
    A = imos(A)
print(*A)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < k; i++) {
    vector<int> b(n + 1);
    for (int j = 0; j < n; j++) {
      int l = max(0, i - a[i]);
      int r = min(n, i + a[i]);
      b[l]++;
      b[r]--;
    }
    for (int j = 0; j < n; j++) {
      b[i + 1] += b[i];
    }
    b.pop_back();
    if (a == b) break;
    a = b;
  }
  for (int i = 0; i < n; i++) {
    cout << a[i] << (i == n - 1 ? '\n' : ' ');
  }
  return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate
from numba import njit

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

@njit(cache=True)
def solve(n, k, a):
    if n == 0:
        return
    for _ in range(k):
        b = [0]*n
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        a = list(accumulate(b))
        if min(a) >= n:
            break
    print(*a)
    return

solve(0, 0, 0)
n, k = nm()
a = nl()
solve(n, k, a)

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate
from numba import njit

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

@njit(cache=True)
def solve():
    n, k = nm()
    a = nl()
    for _ in range(k):
        b = [0]*n
        for i in range(n):
            if i > a[i]:
                b[i-a[i]] += 1
            else:
                b[0] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        a = list(accumulate(b))
        if min(a) >= n:
            break
    print(*a)
    return

solve()

Submission status: Runtime Error

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


import numpy as np
import math

t= min(k, math.log2(n)+5)


for k in range(t):
    bn = np.zeros(n, dtype=int)
    for i in range(n):
        bn[max(i - an[i], 0)] += 1

        if i+ an[i]+1 <n:
            bn[i+an[i]+1] -=1

    an = np.cumsum(bn)


print(*an)

Submission status: Runtime Error

Solution code:
import math
stdin = [input() for i in range(2)]
line = stdin[0].split(' ')
N = int(line[0])
K = int(line[1])
line = stdin[1].split(' ')
Ai = [0]*N
for i in range(len(line)):
    Ai[i] = int(line[i])
if(Ai == [0]*N):
    print (' '.join(Ai))
    exit()
if(K> math.log(N)):
    print ('N '*10)
    exit()
for i in range(K):
    Bi = [1]*N
    for i, d in enumerate(Ai):
        for j in range(1,d+1):
            if i-j >=0:
                Bi[i-j] +=1
            if i+j <N:
                Bi[i+j] +=1
    Ai = Bi
    if Ai[0] == N & Ai[-1] == N:
        break
print(' '.join(Ai))

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate

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

current_arr = A
if K > 41:
    print(" ".join([N]*N))
else:
    for _ in range(K):
        imos = [0] * N
        ruiseki = [0] * (N+1)
        for i, ai in enumerate(current_arr):
            imos[max([0, i-ai])] += 1
            if i+ai+1 < N:
                imos[i+ai+1] -= 1
        for j, im in enumerate(imos):
            ruiseki[j+1] = ruiseki[j] + im
        current_arr = ruiseki[1:]
#print(imos)
#print(ruiseki)
#print(*accumulate(imos))
    print(*current_arr)

Submission status: Runtime Error

Solution code:

def action(A, N):
  B = [0] * (N + 1)
  for i, bright in enumerate(A):
    s = max(0, i - bright)
    B[s] += 1
    e = min(N, i + bright)
    B[e + 1] -= 1
  
  for i in range(N):
    B[i + 1] += B[i]
  return B[:-1]

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

  for i in range(K):
    A = action(A, N)
    if A[0] == N & all(A):
      break
      
  print(*A, sep=" ")

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
import numpy as np
# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))


l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    B=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index >N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        cumulative_sum[0] =B[0]       
        for i in range(1,N):
            cumulative_sum[i] =cumulative_sum[i-1] +B[i]

        A =cumulative_sum
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
        cumulative_sum =[0]*N
    
print(*A)

Submission status: Runtime Error

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

# imos法して，もう一回同じことを行う
# K回のシミューレション，途中で全てがKになったら打ち切る
for _ in range(K):
    new = [0] * N
    imos = [0] * N
    for i, a in enumerate(A):  # 0-indexにしても問題ない
        imos[max(0, i-a)] += 1
        if i+a+1 <= N-1:  # 右端まで照らすなら，終端は管理しない
            imos[i+a+1] -= 1
    for i in range(N):
        new = new[i-1] + imos[i]
    # Aを上書き
    A = new
    if sum(A) == N*N:
        break
print(*A)

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

@njit
def main():

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

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

    for k in range(K):
        B=[0]*(N+1)
        for i in range(N):
            a=A[i]
            start=max(0,i-a)
            end=min(N,i+a+1)
            B[start]+=1
            B[end]-=1
        B=np.array(B)
        A=np.cumsum(B)[:N]
        if A.min()==N:
            break   
    print(*A)

if __name__=="__main__":
    main()

Submission status: Runtime Error

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

da=[0 for i in range(N)]
for k in range(K):
    B=[0 for i in range(N)]
    for i in range(N):
        l=max(0,i-A[i])
        r=min(N-1,i+A[i])
        B[l]=B[l]+1
        if(r+1<N):
            B[r+1]=B[r+1]-1
    for i in range(1,N):
        B[i]=min(N,B[i]+B[i-1])
    A=B
b=[str(i) for i in B]
b=" ".join(b)
print(b)