Problem:


Score : 600 points

Problem Statement

Takahashi is playing a board game called Sugoroku.

On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.

The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.

Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.

Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^5

|S| = N + 1

S consists of 0 and 1.

S[0] = 0

S[N] = 0

Input

Input is given from Standard Input in the following format:

N M
S

Output

If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.

If Takahashi cannot win the game, print -1.

Sample Input 1

9 3
0001000100

Sample Output 1

1 3 2 3

If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.

Sample Input 2

5 4
011110

Sample Output 2

-1

Takahashi cannot reach Square 5.

Sample Input 3

6 6
0101010

Sample Output 3

6



Sample input:
9 3
0001000100


Sample output:
1 3 2 3

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from copy import deepcopy
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, S):
    def f(s, p):
        print(len(s), p)
        if p == 0:
            return s
        elif p < 0:
            return None
        for i in range(M, 0, -1):
            j = p - i
            if j > len(S):
                continue
            if S[j] == '1':
                continue
            s.append(i)
            v = f(s, j)
            if v:
                return v
            s.pop()
        return None
    
    m = 0
    mm = 0
    for c in S:
        if c == '1':
            mm += 1
            m = max(mm, m)
        else:
            mm = 0

    if m >= M:
        return -1
    ans = f([], N)
    if ans:
        return ' '.join(map(str, reversed(ans)))
    return -1
            

        



def main():
    N, M = read_int_n()
    S = read_str()
    print(slv(N, M, S))

    # N = 10**5
    # M = random.randint(1, N)
    # M = 10
    # S =  ''.join(['0'] + random.choices('01',weights=(10, 1), k=N-1) + ['0'])
    # print(N, M, S)
    # print(slv(N, M, S))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from copy import deepcopy
sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, S):
    ans = []
    p = N
    
    def f(s, p):
        if p == 0:
            return s
        elif p < 0:
            return None
        for i in range(M, 0, -1):
            j = p - i
            if S[j] == '1':
                continue
            s.append(i)
            v = f(s, j)
            if v:
                return v
            s.pop()
        return None

    ans = f([], N)
    if ans:
        return ' '.join(map(str, reversed(ans)))
    return -1
            

        



def main():
    N, M = read_int_n()
    S = read_str()
    print(slv(N, M, S))

    # N = 10**5
    # M = N
    # S = '0' * (N+1)
    # print(slv(N, M, S))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    S = f_i.readline().rstrip()
    
    M *= -1
    pos = N
    rec = deque()
    while pos:
        for move in range(M, 0):
            next_pos = pos + move
            if S[next_pos] == '0' and next_pos >= 0:
                pos = next_pos
                rec.appendleft(move)
                break
        else:
            print(-1)
            break
    else:
        print(' '.join(str(-move) for move in rec))

solve()

Submission status: Runtime Error

Solution code:
def solve():
    from heapq import heappush, heappop
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    M *= -1
    S = f_i.readline().rstrip()
    
    unvisited = [True] * (N + 1)
    unvisited[N] = False
    rec = [[] for i in range(N + 1)]
    hq = [(0, N)] # (cost, pos)
    
    while hq:
        cost, pos = heappop(hq)
        if pos == 0:
            break
        
        cost += 1
        for r in range(M, 0):
            next_pos = pos + r
            if unvisited[next_pos] and S[next_pos] == '0':
                unvisited[next_pos] = False
                rec[next_pos] = [r] + rec[pos]
                heappush(hq, (cost, next_pos))
    else:
        return -1
    
    return ' '.join(str(-r) for r in rec[0])

print(solve())

Submission status: Runtime Error

Solution code:
def solve():
    from heapq import heappush, heappop
    from sys import stdin
    #f_i = stdin
    f_i = open('146_F_in_s3')#
    
    N, M = map(int, f_i.readline().split())
    M *= -1
    S = f_i.readline().rstrip()
    
    unvisited = [True] * (N + 1)
    unvisited[N] = False
    rec = [[] for i in range(N + 1)]
    hq = [(0, N)] # (cost, pos)
    
    while hq:
        cost, pos = heappop(hq)
        if pos == 0:
            break
        
        cost += 1
        for r in range(M, 0):
            next_pos = pos + r
            if unvisited[next_pos] and S[next_pos] == '0':
                unvisited[next_pos] = False
                rec[next_pos] = [r] + rec[pos]
                heappush(hq, (cost, next_pos))
    else:
        return -1
    
    return ' '.join(str(-r) for r in rec[0])

print(solve())

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = input()

# dp[i] := ゴールから最短何手でマスiにたどり着けるか
dp = [float('inf')] * (N + 1)
dp[-1] = 0


class RangeMinimumQuery:
    def __init__(self, n, inf=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INF = inf
        self.segtree = [self.INF] * (2 * self.n)

    # i番目の値(0-indexed)をxに変更
    def update(self, i, x):
        i += self.n
        self.segtree[i] = x
        while i > 0:
            i //= 2
            self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

    # [l, r)のmin
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        R = min(R, len(self.segtree) + 1)
        s = self.INF
        while L < R:
            if L & 1:
                s = min(s, self.segtree[L])
                L += 1

            if R & 1:
                s = min(s, self.segtree[R - 1])
                R -= 1

            L >>= 1
            R >>= 1

        return s


# セグメント木でdpテーブルを高速に埋める
RMQ = RangeMinimumQuery(N + 1)
RMQ.update(N, 0)
for i in range(N - 1, -1, -1):
    if S[i] == '1':
        continue

    # RMQ.query(l, r) := [l, r)の最小値
    dp[i] = RMQ.query(i, i + M + 1) + 1
    RMQ.update(i, dp[i])


ans = []
position = 0
while position < N:
    for move in range(1, M + 1):
        if position + move > N:
            continue

        if S[position + move] == '1':
            continue

        # 最短手数にならない
        if dp[position + move] == dp[position]:
            continue

        ans.append(move)
        position += move
        break

    else:
        print(-1)
        exit()

print(*ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
S,r,s=input(),[],N-M
for _ in range(2*N):
    if S[s]=='1':
        s += 1
    else:
        r.append(str(N-s))
        N,s=s,max(0,s-M)
    if N == 0:
        break
print(*[-1] if s else r[::-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
S,r,s=input(),[],N-M
for _ in range(2*N):
    if S[s]=='1':
        s += 1
    else:
        r.append(str(N-s))
        N,s=s,max(0,s-M)
    if s == 0:
        break
print(-1 if s else " ".join(r[::-1]).strip('0 '))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = list(map(int, input()))

memo = [None] * (N + 1)
route = [None] * (N + 1)
memo[0] = 0

import heapq

def dp(pos):
    if memo[pos] != None: return memo[pos]
    #
    ret, pos_prev = (10 ** 9 + 7, None)
    for i in range(M):
        if S[pos - M + i] == 1:
            continue
        elif pos - M + i >= 0:
            if ret > dp(pos - M + i) + 1:
                ret = dp(pos - M + i) + 1
                pos_prev = pos - M + i
        else:
            continue
    #
    memo[pos] = ret
    if pos != None: route[pos] = pos_prev
    # print("#", pos, ret, memo)
    return ret

import sys
sys.setrecursionlimit(10 ** 6)

rslt = dp(N)

# print("#", memo)
# print("#", route)
if rslt >= 10 ** 9 + 7:
    print(-1)
else:
    ans_pos = []
    pos = N
    while True:
        if pos == 0:
            break
        else:
            ans_pos.append(pos)
            pos = route[pos]
    ans_pos.append(0)
    #
    ans = [ans_pos[i] - ans_pos[i + 1] for i in range(len(ans_pos) - 1)]
    print(' '.join(map(str, ans[::-1])))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = list(map(int, input()))

memo = [None] * (N + 1)
route = [None] * (N + 1)
memo[0] = 0

for i, Si in enumerate(S):
    if Si == 1: memo[i] = 10 ** 9 + 7

import heapq

def dp(pos):
    if memo[pos] != None: return memo[pos]
    #
    rets = []
    for i in range(M):
        if S[pos - M + i] == 1:
            continue
        elif pos - M + i >= 0:
            heapq.heappush(rets, (dp(pos - M + i) + 1, pos - M + i))
        else:
            continue
    #
    ret, pos_prev = heapq.heappop(rets)
    memo[pos] = ret
    route[pos] = pos_prev
    # print("#", pos, ret, memo)
    return ret

import sys
sys.setrecursionlimit(10 ** 6)

rslt = dp(N)

# print("#", memo)
# print("#", route)
if rslt >= 10 ** 9 + 7:
    print(-1)
else:
    ans_pos = []
    pos = N
    while True:
        if pos == 0:
            break
        else:
            ans_pos.append(pos)
            pos = route[pos]
    ans_pos.append(0)
    #
    ans = [ans_pos[i] - ans_pos[i + 1] for i in range(len(ans_pos) - 1)]
    print(' '.join(map(str, ans[::-1])))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = list(map(int, input()))

memo = [None] * (N + 1)
route = [None] * (N + 1)
memo[0] = 0

import heapq

def dp(pos):
    if memo[pos] != None: return memo[pos]
    #
    rets = []
    for i in range(M):
        if S[pos - M + i] == 1:
            continue
        elif pos - M + i >= 0:
            heapq.heappush(rets, (dp(pos - M + i) + 1, pos - M + i))
        else:
            continue
    #
    if len(rets) == 0: return 10 ** 9 + 7
    ret, pos_prev = heapq.heappop(rets)
    memo[pos] = ret
    route[pos] = pos_prev
    # print("#", pos, ret, memo)
    return ret

import sys
sys.setrecursionlimit(10 ** 5)

rslt = dp(N)

# print("#", memo)
# print("#", route)
if rslt >= 10 ** 9 + 7:
    print(-1)
else:
    ans_pos = []
    pos = N
    while True:
        if pos == 0:
            break
        else:
            ans_pos.append(pos)
            pos = route[pos]
    ans_pos.append(0)
    #
    ans = [ans_pos[i] - ans_pos[i + 1] for i in range(len(ans_pos) - 1)]
    print(' '.join(map(str, ans[::-1])))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
#sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
s = list(input())
s.reverse()
list1 = []
def maze(mass,times): #今いるマス、現状の手数
  if mass+m >= n:
    list1.append(str(n-mass))
    return
  for i in range(m,0,-1):
    if s[mass+i] == "0":
      list1.append(str(i))
      maze(mass+i,times+1)
      return
    elif i == 1:
      print("-1")
      exit()
  return

a = maze(0,0)
list1.reverse()
print(" ".join(list1))

Submission status: Runtime Error

Solution code:
from sys import stdin

# stdin = open("testdata.txt", "r")

def input():
	return stdin.readline().strip()

from collections import deque

n, m = map(int, input().split())

s = input()

def bfs(src):
	que = deque([[src, []]])
	visited = {src, }

	while que:
		u, path = que.popleft()
		if u == 0:
			return path
		for i in range(m, 0, -1):
			next_pos = u - i
			if next_pos not in visited and next_pos <= n and s[next_pos]=='0':
				visited.add(next_pos)
				que.append((next_pos, path+[i]))
	return -1

ans = bfs(n)
if ans == -1:
	print(ans)
else:
	print(*ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
sys.setrecursionlimit(pow(10, 9))

# stdin = open("testdata.txt", "r")

def input():
	return stdin.readline().strip()

from collections import deque

n, m = map(int, input().split())

s = input()

def bfs(src):
	que = deque([[src, []]])
	visited = {src, }

	while que:
		u, path = que.popleft()
		if u == n:
			return path
		for i in range(1, m+1):
			next_pos = u + i
			if next_pos not in visited and next_pos <= n and s[next_pos]=='0':
				visited.add(next_pos)
				que.append((next_pos, path+[i]))
	return -1

ans = bfs(0)
if ans == -1:
	print(ans)
else:
	print(*ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
S=list(input())
S=S[::-1]
ans=[]
P=0
for i in range(1,N+1):
    if P==N:
        break
    for j in range(M+1):
        if P+(M-j)<=N and S[P+(M-j)]=="0":
            ans.append(M-j)
            P+=M-j
            if M-j==:
                print(-1)
                exit()
            break
ans=ans[::-1]
if 0 in ans:
    print(-1)
else:
    print(*ans)

Submission status: Runtime Error

Solution code:
def main():
	n, m = map(int, input().split())
	rev = input()[::-1]
	ans = []
	cur = 0
	while cur < n:
		for i in range(cur + 1, cur + m + 1):
			if i==n:
				nxt = i
				break
			if rev[i]=="0":
				nxt = i
		if cur==nxt:
			print(-1)
			exit()
		ans += [nxt - cur]
		cur = nxt
		if cur==n:
			break
	print(" ".join(map(str, ans[::-1])))


if __name__=="__main__":
	main()

Submission status: Runtime Error

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

ans = []
x = len(S) - 1
while x:
    for step in range(m, 0, -1):
        to = S[x-step]
        if x - step < 0:
            continue
        if to == '1':
            continue
        else:
            x -= step
            ans.append(str(step))
            break
    else:
        print(-1)
        exit()

print(' '.join(ans[::-1]))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = input()
N0 = 2**(N-1).bit_length()
INF = 2**31-1

# k番目の要素をxに更新
def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s



data1 = [INF]*(2*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(max(0,n-M+1),n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(2*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(max(0,n-M+1),n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = input()
N0 = 2**(N+1).bit_length()
INF = 2**31-1

# k番目の要素をxに更新
def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s



data1 = [INF]*(2*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(2*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = input()
N0 = 2**N.bit_length()
INF = 2**31-1

# k番目の要素をxに更新
def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s



data1 = [INF]*(2*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(2*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = input()
N0 = 2**(N-1).bit_length()
INF = 2**31-1

# k番目の要素をxに更新
def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s



data1 = [INF]*(2*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(2*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    import sys

    input = sys.stdin.readline

    # seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)
    class SegmentTreeClass:
        # original: @solzard_
        # https://twitter.com/solzard_/status/1180263831596982273
        def __init__(self,
                     init_val: 'initial value: iterable',
                     segfunc: 'operation unique in case',
                     ide_ele: 'identity element corresponding init_val' = 0,
                     ):
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.size = 1 << (len(init_val) - 1).bit_length()
            self.tree = self._build(init_val)

        def _build(self, init_val) -> 'tree':
            segfunc = self.segfunc

            tree = [self.ide_ele] * (self.size * 2 - 1)

            for idx, val in enumerate(init_val, self.size - 1):  # set
                # modify val if needed (e.g. str -> ord())
                tree[idx] = val

            for idx in range(self.size - 2, -1, -1):  # build
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

            return tree

        def update(self, idx: int, val) -> None:
            tree = self.tree
            segfunc = self.segfunc

            idx += self.size - 1
            # modify val if needed as same as in _build()
            tree[idx] = val
            while idx > 0:
                idx = (idx - 1) // 2
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        def query(self, left: int, right: int) -> 'result':
            left += self.size
            right += self.size
            ret = self.ide_ele  # left >= right: return self.ide_ele
            segfunc = self.segfunc
            tree = self.tree
            while left < right:  # どの段も奇偶...順
                if left & 1:  # odd
                    ret = segfunc(ret, tree[left - 1])
                    left += 1
                if right & 1:  # odd
                    right -= 1
                    ret = segfunc(ret, tree[right - 1])
                left >>= 1
                right >>= 1
            return ret

    n, m = map(int, input().split())
    s = tuple(map(int, input().rstrip()))

    inf = 10 ** 5 + 10
    dp = [inf] * (n + 1)
    dp[0] = 0
    # dp[x]:=xへの最小到達回数

    seg = SegmentTreeClass(init_val=dp, segfunc=min, ide_ele=inf)

    for j, s_ in enumerate(s[1:], 1):
        if s_:
            continue
        seg.update(j, seg.query(j - m, j) + 1)

    if seg.tree[seg.size - 1 + n] >= inf:
        print(-1)
        return

    order = []
    cf = seg.tree[seg.size - 1 + n] - 1
    cand = inf
    p = seg.size - 1 + n
    for idx in range(seg.size - 1 + n - 1, seg.size - 1 - 1, -1):
        if seg.tree[idx] == cf:
            cand = min(cand, idx)
        elif seg.tree[idx] < cf:
            order.append(p - cand)
            p = cand
            cf -= 1
    order.append(p - idx)

    order.reverse()

    print(*order)
    return


solve()

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


INF = -float('inf')
N, M = map(int, input().split())
S = input()[:-1]
Seg = SegmentTree(N+1, lambda a, b: max(a, b), INF)
for i, c in enumerate(reversed(S)):
    if c == "0":
        Seg.set(i, i)
Seg.build()
ans = []
cur = 0

while True:
    nex = Seg.query(cur+1, min(cur+M+1, N+1))
    if nex == INF:
        ans = [-1]
        break
    else:
        ans.append(nex-cur)
        cur = nex
        if cur == N:
            break
print(" ".join(map(str, reversed(ans))))

    else:
        ans.append(nex-cur)
        cur = nex
        if cur == N:
            break
print(" ".join(map(str, reversed(ans))))

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


INF = -float('inf')
N, M = map(int, input().split())
S = input()[:-1]
Seg = SegmentTree(N+1, lambda a, b: max(a, b), INF)
for i, c in enumerate(reversed(S)):
    if c == "0":
        Seg.set(i, i)
Seg.build()
ans = []
cur = 0

while True:
    nex = Seg.query(cur+1, cur+M+1)
    if nex == INF:
        ans = [-1]
        break
    else:
        ans.append(nex-cur)
        cur = nex
        if cur == N:
            break
print(" ".join(map(str, reversed(ans))))

Submission status: Runtime Error

Solution code:
N0 = 2**(N-1).bit_length()
INF = 2**31-1

# k番目の要素をxに更新
def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

N,M = map(int,input().split())
S = input()

data1 = [INF]*(2*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(2*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)