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:


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


class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        # self.array[actual_x] = self.operator(self.array[actual_x],val)
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

    def find(self, l, r):
        #findの方が高速?
        l += self.num_leaves
        r += self.num_leaves+1
        ret = self.identity
        while l < r:
            if l & 1:
                ret = self.operator(ret, self.array[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.operator(ret, self.array[r])
            l //= 2
            r //= 2
        return ret

st = segtree(n+1,min,1e10)

arr = [1e9 for i in range(n+1)]
arr[0] = 0

st.build(arr)

for i in range(1,n+1):
    if s[i] == "1":
        continue
    else:
        left = max(i-m,0)
        right = i-1
        tm = st.find(left,right)
        arr[i] = tm+1
        st.update(i,tm+1)


nowm = arr[-1]
ans = []
for i in range(2,n+2):
    if nowm > arr[-i]:
        nowm = arr[-i]
        ans.append(-i)
    elif nowm == arr[-i]:
        ans[-1] = -i

# print(arr)
# print(ans)

bef = -1
anss = ""
for a in ans:
    anss += str(bef-a)+" "
    bef = a
anss = anss[:-1]
print(anss[::-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
s = [int(i) for i in list(input())]
INF = float('inf')
dp =[INF]*(n+1)
dp[0] = 0

from collections import defaultdict
route = defaultdict(list)

for i in range(n):
    for j in range(1,m+1):
        if i+j >= n+1: break
        if s[i+j]==1:
            dp[i+j] = INF
            continue
        if dp[i+j] > dp[i]+1:
            dp[i+j] = dp[i]+1
            route[i+j]=(i,j)

i=0
now,m = route[n]
ans = [m]
while now > 0:
    now,m = route[now]
    ans.append(m)


if dp[n]==INF:
    print(-1)
    exit()

ans.reverse()

print(*ans,sep=' ')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
s = [int(i) for i in list(input())]
INF = float('inf')
dp =[INF]*(n+m)
dp[0] = 0

s = s+[0]*m

from collections import defaultdict
route = defaultdict(list)

for i in range(n):
    for j in range(1,m+1):
        if i+j >= n+m-1: break
        if s[i+j]==1:
            dp[i+j] = INF
            continue
        if dp[i+j] > dp[i]+1:
            dp[i+j] = dp[i]+1
            route[i+j]=(i,j)

i=0
now,m = route[n]
ans = [m]
while now > 0:
    now,m = route[now]
    ans.append(m)


if dp[n]==INF:
    print(-1)
    exit()

ans.reverse()

print(*ans,sep=' ')

Submission status: Runtime Error

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

now = n
ans_rev = []
while(now != 0):
    for i in range( now-m,now+1):
        if(i == now):
            print(-1)
            exit()
        if(s[i] == '1'):
            continue

        ans_rev.append(now - i)
        now = i
        break

print(' '.join(map(str, ans_rev[::-1])))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
s = input()
len_s = len(s)
inf = 10 ** 18
dp = [[inf,inf] for _ in range(len_s)] # [iまでの手数,一つ前のマス]
for i in range(1, m+1):
    if s[i] == "0":
        dp[i][0] = 1
        dp[i][1] = 0
for i in range(m+1, n+1):
    if i == "1":
        continue
    for j in range(1, m+1)[::-1]:
        if dp[i][0] > dp[i-j][0] + 1:
            dp[i][0] = dp[i-j][0] + 1
            dp[i][1] = i - j
if dp[-1][0] == inf:
    print(-1)
else:
    ans = ""
    x = len_s - 1
    while x > 0:
        ans = str(x - dp[x][1]) + " " + ans
        x = dp[x][1]
    print(ans.strip())

Submission status: Runtime Error

Solution code:
n= int(input())
a = list(map(int,input().split()))
now = a[0] 
a.sort()
res = 0
ans = 1
for i in range(n-1):
    if a[i+1] != now:
        ans+=1
        now = a[i+1]
if ans%2:print(ans)
else: print(ans-1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=input()
ans=[]
def f(i,j):
    if i==0:
        print(" ".join(map(str,ans[::-1])))
        return
    if j>i:
        j=i
    while s[i-j]=="1":
        j-=1
    if j==0:
        print(-1)
        return
    ans.append(j)
    f(i-j,m)
f(n,m)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=input()
ans=[]
def f(i,j):
    if i==0:
        return
    if j>i:
        j=i
    while s[i-j]=="1":
        j-=1
    if j==0:
        print(-1)
        quit()
    ans.append(j)
    f(i-j,m)
f(n,m)
print(" ".join(map(str,ans[::-1])))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=input()
l=[0 for i in range(n+1)]
i=0
j=0
while j<n:
    j+=1
    while s[j]=="1":
        j+=1
    while j>i:
        i+=1
        l[i]=j
ans=[[] for i in range(n+1)]
for i in range(1,m+1):
    ans[i].append(i)
for i in range(m+1,n+1):
    if s[i]=="1":
        continue
    else:
        ans[i]=ans[l[i-m]]+[i-l[i-m]]
if 0 in ans[-1]:
    print(-1)
else:
    print(" ".join(map(str,ans[-1])))

Submission status: Runtime Error

Solution code:
#146_F
n, m = map(int, input().split())
s = input()

dp = [[] for _ in range(n+1)]
for i in range(1, n+1):
    if s[i] == '1':
        continue
    l = []
    for j in range(1, m+1):
        if s[i-j] == '1':
            continue
        if i - j < 0:
            continue
        l.append([len(dp[i-j]) + 1, dp[i-j] + [j]])
        
    if len(l) == 0:
        dp[n] = [-1]
        break
        
    l.sort()
    dp[i] = l[0][1]
    
print(*dp[n])

Submission status: Runtime Error

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

idx = n
ans=[]
while idx > 0:
    for i in range(1,m+1)[::-1]:
        #print(i,idx,idx-i,S[idx-i])
        if S[idx-i] == 0 and idx-i>=0:
            idx -= i
            ans.append(i)
            break
    else:
        print(-1)
        sys.exit()
print(*ans[::-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = input()
S = S[::-1]

dp = [-1] * (N + 1)
dp[0] = 0

pos = 0
while pos < N:

    p = pos
    update = False

    for i in range(1, M + 1):
        if p + i > N:
            break
        if S[p + i] == "1":
            continue
        update = True
        pos = p + i
        dp[pos] = dp[p] + 1

    if not update:
        break

if dp[N] == -1:
    print(-1)
    exit()

dp = dp[::-1]
num = dp[0]
ans = []
pos = 0

while num > 0:
    for i in range(1, M + 1):
        if dp[pos + i] == num - 1:
            num -= 1
            pos += i
            ans.append(str(i))

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, S: str):

    # 最短手数を求める
    DP = [INF]*(N+1)
    DP[0] = 0
    for i in range(1, N+1):
        if S[i] == "1":
            continue
        for j in range(1, M+1):
            if i-j < 0:
                break
            DP[i] = min(DP[i], DP[i-j]+1)

    if DP[-1] == INF:
        print(-1)
        return
    # 逆順に辿って実際の手を求める
    # 辞書順になるよう、後ろから貪欲に選ぶ
    ans = []
    curr = N
    while curr > 0:
        for i in range(M, 0, -1):
            if curr-i == 0:
                break
            if DP[curr-i] < DP[curr]:
                break
        curr = curr - i
        ans.append(i)
    print(*reversed(ans), sep=" ")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, M, S)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

for i in range(1, N+1):
    if S[i] == '1':
        continue
    else:
        prv_dp_val = dp[i]
        for j in range(1, M+1):

            if dp[i-j] is not None:
                if dp[i] is None:
                    dp[i] = i - j
                else:
                    dp[i] = min(dp[i], i - j)

if dp[-1] is None:
    print(-1)
else:
    ans = []
    idx = N
    while idx > 0:
        ans.append(idx - dp[idx])
        idx = dp[idx]
    print(*ans[::-1])

Submission status: Runtime Error

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

dp = [None for _ in range(N+1)]
dp[0] = -1

for i in range(1, N+1):
    if S[i] == '1':
        continue
    else:
        prv_dp_val = dp[i]
        for j in range(1, M+1):

            if dp[i-j] is not None:
                if dp[i] is None:
                    dp[i] = i - j
                else:
                    dp[i] = min(dp[i], i - j)

if dp[-1] is None:
    print(-1)
else:
    ans = []
    idx = N
    while idx > 0:
        ans.append(idx - dp[idx])
        idx = dp[idx]
    print(*ans[::-1])

Submission status: Runtime Error

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

steps = [[] for i in range(N)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if root[N] == -1:
  ans = -1
else:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)

Submission status: Runtime Error

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

steps = [[] for i in range(N)]
steps[0] = [0]
num_steps = 0
root = [0] + [-1]*N
pos = 1

while pos <= N:
  starts = steps[num_steps]
  if not starts:
    ans = -1
    break
  for start in starts:
    end = min(start+M+1, N+1)
    for i in range(pos, end):
      if S[i] == '0':
        steps[num_steps+1].append(i)
        root[i] = start
    
    pos = end
  
  num_steps += 1


if pos == N+1:
  pos = N
  ans = []
  while pos > 0:
    pre_pos = root[pos]
    ans.append(str(pos - pre_pos))
    pos = pre_pos
  
  ans = ans[::-1]
  ans = ' '.join(ans)


print(ans)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
import numpy as np

def main():
	n,m=map(int,input().split())
	s=input().rstrip().decode('utf-8')
	t=s[::-1]
	
	ans=[]
	
	now=0
	while now<n:
		for i in range(min(m,n-now),0,-1):
			
			if t[now+i]=="0":
				now+=i
				ans.append(i)
				break
			else:
				continue
		else:
			print(-1)
			exit(0)
	
	print(*ans[::-1])
	
	
	
	
	
	
	



if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

# 現在位置
now = 0
_now = 0
ans = []
while now <= N-1:
    for i in range(M, 0, -1):
        if now+i > N:
            continue
        if S[now+i] == '0':
            ans.append(i)
            now += i
    if _now == now:
        print(-1)
        exit()
    _now = now

# 辞書順最小化を目指す
ans = sorted(ans)
new_ans = []
now = 0
while len(ans) > 0:
    length = 0
    for a in ans:
        if S[now+a] == '0':
            new_ans.append(a)
            now += a
            length = a
            break
    ans.remove(length)
print(*new_ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)

N, M = [int(n) for n in input().split()]
S = input()

ans = []

def rest(l, ans):
    s = M
    while s > 0:
        if s >= l:
            ans.append(l)
            return ans
        if S[l-s] == "1":
            if s == 1:
                return -1
            s -= 1
            continue
        l -= s
        if rest(l, ans) == -1:
            s -= 1
        else:
            ans.append(s)
            return ans
    return -1

ans = rest(N, [])

if ans == -1:
    print(-1)
else:
    print(" ".join([str(n) for n in ans]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100001)

N, M = [int(n) for n in input().split()]
S = input()

ans = []

def rest(l):
    s = M
    while s > 0:
        if s >= l:
            ans.append(l)
            return True
        if S[l-s] == "1":
            if s == 1:
                return -1
            s -= 1
            continue
        l -= s
        if rest(l) == -1:
            s -= 1
        else:
            ans.append(s)
            return True
    return -1

rest(N)

if len(ans) == 0:
    print(-1)
else:
    print(" ".join([str(n) for n in ans]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N, M = [int(n) for n in input().split()]
S = input()

ans = []

def rest(l):
    s = M
    while s > 0:
        if s >= l:
            ans.append(l)
            return True
        if S[l-s] == "1":
            if s == 1:
                return -1
            s -= 1
            continue
        l -= s
        if rest(l) == -1:
            s -= 1
        else:
            ans.append(s)
            return True

rest(N)

if len(ans) == 0:
    print(-1)
else:
    print(" ".join([str(n) for n in ans]))

Submission status: Runtime Error

Solution code:
N, M = [int(n) for n in input().split()]
S = input()

ans = []

def rest(l):
    s = M
    while s > 0:
        if s >= l:
            ans.append(l)
            return True
        if S[l-s] == "1":
            if s == 1:
                return -1
            s -= 1
            continue
        l -= s
        if rest(l) == -1:
            s -= 1
        else:
            ans.append(s)
            return True

rest(N)

if len(ans) == 0:
    print(-1)
else:
    print(" ".join([str(n) for n in ans]))

Submission status: Runtime Error

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

g = n 
x = []
while g > 0:
    g -= m 
    count = m
    while s[g]=='1':
        g += 1
        count -= 1
    x.append(count)
x[-1] = n - sum(x[1:])

x.reverse()
for i in range(len(x)):
    print(x[i], end=" ")

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
S=input()
math=['']+['0' if S[i]=='0' else '-1' for i in range(1, N)]+['0']
for i in range(1, min(N+1, M+1)):
  if math[i]=='0':
    math[i]=str(i)
    
i=M+1
while i<N+1:
  if math[i]=='0':
    for j in range(M, 0, -1):
      if math[i-j]!='-1':
        math[i]=math[i-j]+' '+str(j)      
        break
    if math[i]=='0':
      math[i]='-1'
  i+=1
  
print(math)

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
S=input()
math=['']+['0' if S[i]=='0' else '-1' for i in range(1, N)]+['0']
for i in range(1, min(N+1, M+1)):
  if math[i]=='0':
    math[i]=str(i)
    
i=M+1
while i<N+1:
  for j in range(M, 0, -1):
    if math[i-j]!='-1':
      math[i]=math[i-j]+' '+str(j)      
      break
  if math[i]=='0':
    math[i]='-1'
  i+=1
  
print(math)

Submission status: Runtime Error

Solution code:
import sys

def back_search(N, M, S):
    result=[]
    search_index = 0
    while(search_index < N):
        prev_search_index = search_index
        for m in reversed(range(1,M+1)):
            if search_index + m > N+1:
                continue
            if S[search_index + m] == '0':
                result.append(m)
                search_index += m
                break
        if prev_search_index == search_index:
            return []
    return result

def forward_search(N, M, S, index, depth):
    result=[]
    if depth is 0:
        if N-index > M:
            return -1
        else:
            result.append(N-index)
            return result
    else :
        search_max = min(M, N-index)+1
        for i in range(1,search_max):
            if S[index + i] is "0":
                sub_result = forward_search(N,M,S,index+i, depth-1)
                if not (sub_result is -1):
                    result.append(i)
                    result.extend(sub_result)
                    return result
        return -1
            

def main():
    input=[]
    for line in sys.stdin:
        input.append(line)

    nums = input[0].split(" ")
    N_number = int(nums[0])
    M_number = int(nums[1])
    S_str = input[1]

    back_result = back_search(N_number, M_number, S_str)

    if not back_result:
        print (-1)
        exit()
    result = forward_search(N_number,M_number,S_str,0,len(back_result)-1)
    print(" ".join(map(str,result)))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split(" ")]
s = input()
 
ans = []
 
s = s[:-1]
while len(s) > 1:
    tail = s[-m:]
    idx = tail.index("0")
    if idx == -1:
        ans = [-1]
        s = "" # To end the game.
    else:
        ans = [m - idx] + ans
        s = s[:-m + idx]
    
print(ans)

Submission status: Runtime Error

Solution code:
n, m = [int(x) for x in input().split(" ")]
s = input()

ans = []

s = [:-1]
while len(s) > 1:
    tail = s[-m:]
    idx = tail.index("0")
    if idx == -1:
        ans = [-1]
        s = "" # To end the game.
    else:
        ans = [m - idx] + ans
        s = [:-m + idx]
    
print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(item) for item in input().split()]
S = input()
a=[]
s = S
n = N
while n > 0:
    for i in range(M, 0, -1):
        can = False
        if n>=i and s[n-i] == '0':
            a.append(i)
            s = s[:n-i+1]
            print(s)
            n -= -i
            can = True
            break
    if not can and len(s)>1:
        print(-1)
        a=[]
        break
a=a[-1::-1]
if len(a):
    print(*a)

Submission status: Runtime Error

Solution code:
#include <cstdio>
#include <iostream>
#include <sstream>

#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

#include <chrono>
#include <random>

using namespace std;
using i64 = int_fast64_t;
using ui64 = uint_fast64_t;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<i64>;
using vvl = vector<vl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pii = pair<int, int>;
using pll = pair<i64, i64>;

//////////////////////////////////////////////////

int main() { 
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  vector<int> prev(n+1, -1);
  vector<int> t(n+1, -1);
  t[0] = 0;
  function<int(int)> solve = [&](int v){
    if(s[v] == '1')return -1;
    else if(v == 0) return 0;
    else if(t[v] != -1) return t[v];
    int ans = n+1;
    for(int i = max(0, v-m);i!=v;i++){
      int tmp = solve(i);
      if(tmp != -1 && tmp + 1 < ans){
        ans = tmp + 1;
        prev[v] = i;
      }
    }
    return t[v] = (ans == n+1 ? -1 : ans);
  };
  int f = solve(n);
  cerr << f << endl;
  if(f != -1){
    vector<int> ret;
    while(n){
      ret.emplace_back(n - prev[n]);
      n = prev[n];
    }
    reverse(ret.begin(), ret.end());
    for(auto&& x:ret)cout << x << " ";
    cout << endl;
  }else cout << -1 << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

# Range Minimum query
class SegmentTree:

    def __init__(self, N, INF = INF):
        self.N = 1
        while self.N < N:
            self.N <<= 1
        self.data = [INF for i in range((self.N<<1)-1)]

    def update(self, k, a):
        k += self.N-1
        self.data[k] = a
        while k > 0:
            k = (k-1)>>1
            self.data[k] = min(self.data[(k<<1)+1], self.data[(k<<1)+2])

    def RmQ(self, a, b, k=0, l=0, r=-1):
        if r == -1: r = self.N
        if r <= a or b <= l:
            return INF
        if a <= l and r <= b:
            return self.data[k]
        vl = self.RmQ(a, b, (k<<1)+1, l, (l+r)>>1)
        vr = self.RmQ(a, b, (k<<1)+2, (l+r)>>1, r)
        return min(vl, vr)

N, M = map(int, input().split())
S = input()
dp = SegmentTree(N+1)
dp.update(0, 0)
for i in range(1, N+1):
    if S[i] == '0':
        c = dp.RmQ(max(0, i-M), i)
        if c != INF:
            dp.update(i, c+1)
G = dp.RmQ(N, N+1)
if G == INF:
    print(-1)
    exit()
minv = [INF] * N
for i in range(N)[::-1]:
    if S[i] == '0':
        x = dp.RmQ(i, i+1)
        minv[x] = i
minv[G] = N
x = 0
vs = []
while x <= G:
    vs.append(minv[x])
    x += 1
vs = vs[::-1]
ans = [vs[i]-vs[i+1] for i in range(len(vs)-1)]
print(*ans[::-1], sep = ' ')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

# Range Minimum query
class SegmentTree:

    def __init__(self, N, INF = INF):
        self.N = 1
        while self.N < N:
            self.N *= 2
        self.data = [INF for i in range(self.N*2-1)]

    def update(self, k, a):
        k += self.N-1
        self.data[k] = a
        while k > 0:
            k = (k-1)//2
            self.data[k] = min(self.data[k*2+1], self.data[k*2+2])

    def RmQ(self, a, b, k=0, l=0, r=-1):
        if r == -1: r = self.N
        if r <= a or b <= l:
            return INF
        if a <= l and r <= b:
            return self.data[k]
        vl = self.RmQ(a, b, k*2+1, l, (l+r)>>1)
        vr = self.RmQ(a, b, k*2+2, (l+r)>>1, r)
        return min(vl, vr)

N, M = map(int, input().split())
S = input()
dp = SegmentTree(N+1)
dp.update(0, 0)
for i in range(1, N+1):
    if S[i] == '0':
        c = dp.RmQ(max(0, i-M), i)
        if c != INF:
            dp.update(i, c+1)
G = dp.RmQ(N, N+1)
if G == INF:
    print(-1)
    exit()
minv = [INF] * N
for i in range(N)[::-1]:
    if S[i] == '0':
        x = dp.RmQ(i, i+1)
        minv[x] = i
minv[G] = N
x = 0
vs = []
while x <= G:
    vs.append(minv[x])
    x += 1
vs = vs[::-1]
ans = [vs[i]-vs[i+1] for i in range(len(vs)-1)]
print(*ans[::-1], sep = ' ')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

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

if s.find('1' * m) != -1:
    print(-1)
    exit()

cur_pos = n
route = []
while cur_pos > 0:
    for i in range(m, 0, -1):
        next_pos = cur_pos - i
        if s[next_pos] == '1':
            continue

        if next_pos > 0:
            route.append(i)
            cur_pos = next_pos
            break
        else:
            route.append(cur_pos)
            cur_pos = 0
            break

print(' '.join(map(str, reversed(route))))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

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

if s.find('1' * m) != -1:
    print(-1)
    exit()

cur_pos = n
route = []
while cur_pos > 0:
    for i in range(m, 0, -1):
        next_pos = cur_pos - i
        if s[next_pos] == '1':
            continue
        else:
            if next_pos > 0:
                route.append(i)
                cur_pos = next_pos
                break
            else:
                route.append(cur_pos)
                cur_pos = 0
                break

print(' '.join(map(str, reversed(route))))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import resource
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)
s, h = resource.getrlimit(resource.RLIMIT_STACK)
resource.setrlimit(resource.RLIMIT_STACK, (h, h))
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):
        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))


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