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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

import time
def Dijkstra(num, start, s, m):
    a = time.time()
    dist = [inf for i in range(num)]
    x = -1
    dist[0] = 0
    for i in range(num):
        if time.time() - a > 1:
            print(1)
            return
        if x > i:
            continue
        a = dist[i]
        for k in range(1, m + 1):
            if s[i + k] == "1":
                continue
            dist[i + k] = a + 1
            x = i + k
            if i + k == num-1:
                return dist
    
    return dist


#solve
def solve():
    n, m = LI()
    s = S()
    d = Dijkstra(n + 1, 0, s, m)
    if d[-1] == inf:
        print(-1)
        return
    ans = []
    q = deque([n])
    while q:
        a = q.pop()
        x = d[a]
        for i in range(min(a, m), 0, -1):
            if x - 1 == d[a - i]:
                q.append(a - i)
                ans.append(i)
                break
    ans = ans[::-1]
    print(" ".join(map(str, ans)))
    return


#main
if __name__ == '__main__':
    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, 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:
n, m = [int(s) for s in input().split()]
s = [int(s) for s in input()]
board = [None]*(n+1)
left = 0
for i in range(1,n+1):
    if s[i]:
        continue
    left = max(left, i-m)
    while s[left]:
        left += 1
        if left >= i:
            break
    if left < i:
        board[i] = left
# print(board)
if board[n] is None:
    print(-1)
else:
    steps = []
    j = n
    while True:
        step = j - board[j]
        steps.append(step)
        j = board[j]
        if j==0:
            break
    print(' '.join(str(s) for s in steps[::-1]))

Submission status: Runtime Error

Solution code:
n, m = [int(s) for s in input().split()]
s = [int(s) for s in input()]
board = [None]*(n+1)
left = 0
for i in range(1,n+1):
    if s[i]:
        continue
    left = max(left, i-m)
    while s[left]:
        left += 1
        if left >= i:
            break
    if left < i:
        board[i] = left
print(board)
if board[n] is None:
    print(-1)
else:
    steps = []
    j = n
    while True:
        step = j - board[j]
        steps.append(step)
        j = board[j]
        if j==0:
            break
    print(' '.join(str(s) for s in steps[::-1]))

Submission status: Runtime Error

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

# dp[i]=iに行くのに最短の手数
dp=[0]*(n+1)
ans=0
now=n
count=0
flag=True
ans=[]
for i in range(10**11):
    if flag==False:
        break
    for j in range(m,0,-1):
        if s[now-j]!='1':
            if now-j<=0:
                ans.append(now)
                flag=False
                break
            else:
                ans.append(j)
                count+=1
                now-=j
                break
        else:
            if j==1:
                print(-1)
                exit()
            continue
        

ans.reverse()

print(*ans)

Submission status: Runtime Error

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

# dp[i]=iに行くのに最短の手数
dp=[0]*(n+1)
ans=0
now=n
count=0
flag=True
ans=[]
for i in range (n+1):
    if flag==False:
        break
    for j in range(m,0,-1):

        if s[now-j]!='1':
            if now-j<=0:
                ans.append(now)
                flag=False
                break
            else:
                ans.append(j)
                count+=1
                now-=j
                break
        else:
            if j==1:
                print(-1)
                exit()
            continue
        

ans.reverse()

print(*ans)

Submission status: Runtime Error

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

# dp[i]=iに行くのに最短の手数
dp=[0]*(n+1)
ans=0
now=n
count=0
flag=True
ans=[]
for i in range (n+1):
    if flag==False:
        break
    for j in range(m,0,-1):

        if s[now-j]!='1':
            if now-j<=0:
                ans.append(now)
                flag=False
                break
            else:
                ans.append(j)
                count+=1
                now-=j
                break
        else:
            if j==0:
                print(-1)
                exit()
            continue
        

ans.reverse()

print(*ans)

Submission status: Runtime Error

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()
S = read()[:-1]
S = S[::-1]
ans = []
cur_i = 0
while True:
    dice = M
    cur_i += dice
    if cur_i > N + 1:
        ans.append(N - (cur_i - M))
        break
    if cur_i = N = 1:
        break
    while S[cur_i] == '1':
        cur_i -= 1
        dice -= 1
        if dice == 0:
            print(-1)
            exit()
    ans.append(dice)
print(*ans[::-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
s = input()[::-1]
t  =[]
cnt = 0
st = 0
go = 0
for i in range(len(s)):
    if cnt==M:
        if s[i] == '0':
            t.append(cnt)
            cnt = 0
            go = -1
        else:
            if go==-1 and s[i-1]=='0':
                go = i-1

            if t==[] or  go==-1:
                break
            else:
                t.append(go-t[-1])
                cnt = i-go
                go = -1

    elif s[i] == '1' and s[i-1]=='0':
        go = i-1
    elif i == len(s)-1:
        t.append(cnt)
    cnt += 1

f = False
cnt = 0
for i in s:
    if i=='1':
        cnt += 1
    else:
        cnt = 0
    if cnt>=M:
        f=True
        break
if f:
    print(-1)
else:
    if s[-2]=='1':
        print(*t[-1][::-1])
    else:
        print(*t[::-1])

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_right

N,M = II()
A = list(map(str, input().split()))

B = list(reversed(A))
ones = []
n = [0]*N
for i in range(N):
    if B[i]=='1':
        ones.append(i)

ans = []
place = 0
while place<N-1:
    for i in range(1,M+1)[::-1]:
        if B[place+i]!=1:
            ans.append(i)
            place += i
        if i==1 and B[place+i]=='1':
            print(-1)
            exit()

print(*list(reversed(ans)))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
from collections import deque
import copy
import sys

def check(ps, l, S):
    p = sum(ps)
    if p+l == len(S)-1:
        return 1
    if int(S[p+l]) == 1:
        return -1
    return 0

queue = deque()

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

for i in range(1, M+1):
    queue.appendleft([[0], i])

while True:
    nextqueue = deque()
    if len(queue) == 0:
        print(-1)
        sys.exit()
    while len(queue) != 0:
        ps, l = queue.pop()
        ps_ = copy.deepcopy(ps)
        ret = check(ps, l, S)
        if ret == 1:
            print(*ps[1:], l)
            sys.exit()
        elif ret == 0:
            ps_.append(l)
            for i in range(1, M+1):
                nextqueue.appendleft([ps_, i])
    queue = nextqueue

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=input()
x=n
a=0
while x!=0:
  for i in range(m,0,-1):
    if s[x-i]=="0":
      x-=i
      a=a*10+i
      break
    if i==1:print(-1);exit()
print(*list(str(a))[::-1])

Submission status: Runtime Error

Solution code:
n, m = [int(s) for s in input().split()]
s = [int(s) for s in input()]
board = [None]*(n+1)
left = 0
for i in range(1,n+1):
    if s[i]:
        continue
    left = max(left, i-m)
    while s[left]:
        left += 1
        if left >= i:
            break
    if left < i:
        board[i] = left
if board[n] is None:
    print(-1)
else:
    steps = []
    j = n
    while j > 0:
        step = j - board[j]
        steps.append(step)
        j = board[j]
    print(' '.join(str(s) for s in steps[::-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
from collections import deque
import copy
import sys

def check(ps, l, S):
    p = sum(ps)
    if int(S[p+l]) == 1:
        return -1
    if p+l == len(S)-1:
        return 1
    else:
        return 0

queue = deque()

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

for i in range(1, M+1):
    queue.appendleft([[0], i])

while True:
    nextqueue = deque()
    if len(queue) == 0:
        print(-1)
        sys.exit()
    while len(queue) != 0:
        ps, l = queue.pop()
        ps_ = copy.deepcopy(ps)
        ret = check(ps, l, S)
        if ret == 1:
            print(*ps[1:], l)
            sys.exit()
        elif ret == 0:
            ps_.append(l)
            for i in range(1, M+1):
                nextqueue.appendleft([ps_, i])
    queue = nextqueue

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=list(str(input()))
f=0
mf=0
for i in range(n+1):
    if s[i]=='1':
        f+=1
        mf=max(mf,f)
    else:
        f=0
if mf>=m:
    print(-1)
    exit()
reans=[]
s.reverse()
nk=-1
while nk<n+1:
    for i in range(min(n+1-nk,m),0,-1):
        if s[nk+i]=='0':
            nk=nk+i
            reans.append(i)
            break
reans.reverse()
print(*reans)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
s=input()
co=[[0,0] for i in range(n)]
tmp=0
for i in range(m):
    if s[i+1]=="0":
        tmp=i+1
# print(tmp)
li=[]
for i in range(n+1):
    li.append(tmp)
    a=i+1+m
    if a>n:
        a=n
    if s[a]=="0":
        tmp=a
# print(li)
i=0
while(li[i]!=i):
    print(li[i]-i)
    i=li[i]
    if i==n:
        quit()
print(-1)

Submission status: Runtime Error

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

n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


i = len(move) - 1
move.sort()
n = N
ans = []
while move:
    if S[n - move[i]] != '1':
        ans.append(move[i])
        n -= move[i]
        del move[i]
        i = len(move) - 1
    else:
        i -= 1

print(*ans[::-1])

Submission status: Runtime Error

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

# 後ろから貪欲
ans = []
S = S[::-1]

pos = [N + 1] * len(S)
p = N + 1
l = N
while p - l <= M:
    pos[l] = p
    l -= 1
p -= 1
while p >= 0:
    if S[p] == '1':
        p -= 1
        continue

    while p - l <= M and l >= 0:
        pos[l] = p
        l -= 1
    p -= 1

i = 0
while i < N:
    me = None
    for j in reversed(range(1, min(M + 1, pos[i] - i + 1))):
        if i + j < len(S) and S[i + j] == '0':
            me = j
            break
    if me is None:
        print(-1)
        exit()
    ans.append(me)
    i += me
print(*ans[::-1])

Submission status: Runtime Error

Solution code:
def solve():
    from bisect import bisect_left
    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

    dp = []
    for i, x in enumerate(seg.tree[seg.size - 1:]):
        if x >= inf:
            dp.append(dp[i - 1])
        else:
            dp.append((x, i))

    order = []
    p = 0
    cf = 1
    while p < n:
        if dp[n][0] == cf:
            order.append(n - p)
            break

        idx = bisect_left(dp, (cf, p))
        order.append(dp[idx][1] - p)
        p = idx
        cf += 1

    print(*order)
    return


solve()

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=list(str(input()))
f=0
mf=0
for i in range(n):
    if s[i]=='1':
        f+=1
        mf=max(mf,f)
    else:
        f=0
if mf>=m:
    print(-1)
    exit()
reans=[]
s.reverse()
nk=-1
while nk<n:
    for i in range(m,0,-1):
        if s[nk+i]=='0':
            nk=nk+i
            reans.append(i)
            break
reans.reverse()
print(*reans)

Submission status: Runtime Error

Solution code:
def f():
    n, m = [int(s) for s in input().split()]
    s = [int(s) for s in input()]
    board = [None]*(n+1)
    left = 0
    for i in range(1,n+1):
        if s[i]:
            continue
        left = max(left, i-m)
        while s[left] and left<i:
            left += 1
        if left < i:
            board[i] = left
    if board[n] is None:
        print(-1)
        return
    steps = []
    j = n
    while j > 0:
        step = j - board[j]
        steps.append(step)
        j = board[j]
    print(' '.join(str(s) for s in steps[::-1]))

f()

Submission status: Runtime Error

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()
S = read()[:-1]
S = S[::-1]
ans = []
cur_i = 0
while cur_i < N:
    dice = M
    cur_i += dice
    if cur_i > N + 1:
        ans.append(N - (cur_i - M))
        break
    while S[cur_i] == '1':
        cur_i -= 1
        dice -= 1
        if dice == 0:
            print(-1)
            exit()
    ans.append(dice)
print(*ans[::-1])

Submission status: Runtime Error

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    s = str(readline().rstrip().decode('utf-8'))
    cur = n
    ans = []
    while True:
        b = False
        for i in range(cur - m, cur):
            if s[i] == "0" and i >= 0:
                b = True
                ans.append(cur - i)
                cur = i
                break
        if not b:
            print(-1)
            exit()
        if cur == 0:
            ans.reverse()
            print(*ans)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:

N,M = map(int,input().split())
S = input()
import sys
flag = False
cnt = 0
for i in range(len(S)-1):
    if S[i]=='1' and S[i+1] == '1':
        if flag:
            cnt += 1
            if cnt >= M:
                print(-1)
                sys.exit()
        else:
            cnt = 2
            flag = True
            if cnt >= M:
                print(-1)
                sys.exit()
    else:
        flag = False

if M==1:
    for s in S:
        if s == '1':
            print(-1)
            sys.exit()

if (M>=N):
    print(N)
    sys.exit()
    

dp = [10**9]*(N+M)
dp[0] = 0
keiro = [0] * (N+M)

for i in range(N+1):
    flag = True
    for j in range(1,M+1):
        nxt = i+j
        if (S[nxt]!='1'):
            if dp[nxt]>dp[i]+1:
                dp[nxt] = dp[i]+1
                keiro[nxt] = j
                if nxt == N:
                    flag = False
                    break
    if not(flag):
        break

ans = []
idx = N
while (idx>0):
    ans.append(keiro[idx])
    idx -= keiro[idx]
ans = reversed(ans)
print(*ans)

Submission status: Runtime Error

Solution code:

N,M = map(int,input().split())
S = input()
import sys
flag = False
cnt = 0
for i in range(len(S)-1):
    if S[i]=='1' and S[i+1] == '1':
        if flag:
            cnt += 1
            if cnt >= M:
                print(-1)
                sys.exit()
        else:
            cnt = 2
            flag = True
            if cnt >= M:
                print(-1)
                sys.exit()
    else:
        flag = False

if M==1:
    for s in S:
        if s == '1':
            print(-1)

if (M>=N):
    print(N)
    

dp = [10**9]*(N+M)
dp[0] = 0
keiro = [0] * (N+M)

for i in range(N+1):
    flag = True
    for j in range(1,M+1):
        nxt = i+j
        if (S[nxt]!='1'):
            if dp[nxt]>dp[i]+1:
                dp[nxt] = dp[i]+1
                keiro[nxt] = j
                if nxt == N:
                    flag = False
                    break
    if not(flag):
        break

ans = []
idx = N
while (idx>0):
    ans.append(keiro[idx])
    idx -= keiro[idx]
ans = reversed(ans)
print(*ans)

Submission status: Runtime Error

Solution code:
#ライブラリインポート
from collections import defaultdict
import bisect

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	S = list(input())
	nibu = []
	for i in range(N + 1):
		if S[i] == "0":
			nibu.append(i)
	DP = [0] * (N + 1)
	prev = [None] * (N + 1)
	for i in range(1, N + 1):
		if S[i] == "0":
			s = bisect.bisect_left(nibu, i - M)
			x = nibu[s]
			if x != i:
				prev[i] = x
				DP[i] = DP[x] + 1
	# print(nibu)
	# print(DP)
	# print(prev)
	if prev[N] == None:
		print(-1)
	else:
		ans = []
		x = N
		while True:
			ans.append(x - prev[x])
			x = prev[x]
			if x == 0:
				break
		ans = ans[::-1]
		print(" ".join(list(map(str, ans))))

if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

n = 0
next_n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


print(1 / 0)
# i = len(move) - 1
# move.sort(reverse=True)
# n = 0
# ans = []
# while move:
#     if S[n + move[i]] != '1':
#         ans.append(move[i])
#         n += move[i]
#         del move[i]
#         i = len(move) - 1
#     else:
#         i -= 1
# 
# print(*ans)

Submission status: Runtime Error

Solution code:

N,M = map(int,input().split())
S = input()
import sys
flag = False
cnt = 0
for i in range(len(S)-1):
    if S[i]=='1' and S[i+1] == '1':
        if flag:
            cnt += 1
            if cnt >= M:
                print(-1)
                sys.exit()
        else:
            cnt = 2
            flag = True
            if cnt >= M:
                print(-1)
                sys.exit()
    else:
        flag = False

if M==1:
    for s in S:
        if s == '1':
            print(-1)


dp = [10**9]*(N+1)
dp[0] = 0
keiro = [0] * (N+1)

for i in range(N+1):
    flag = True
    for j in range(1,M+1):
        nxt = i+j
        if (S[nxt]!='1'):
            if dp[nxt]>dp[i]+1:
                dp[nxt] = dp[i]+1
                keiro[nxt] = j
                if nxt == N:
                    flag = False
                    break
    if not(flag):
        break

ans = []
idx = N
while (idx>0):
    ans.append(keiro[idx])
    idx -= keiro[idx]
ans = reversed(ans)
print(*ans)

Submission status: Runtime Error

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

n = 0
next_n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


i = len(move) - 1
move.sort(reverse=True)
n = 0
ans = []
while move:
    if S[n + move[i]] != '1':
        ans.append(move[i])
        n += move[i]
        del move[i]
        i = len(move) - 1
    else:
        i -= 1

print(*ans)

Submission status: Runtime Error

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

N += 1
# Max size of tree  
tree = [0] * (2 * N);  
n = N
# function to build the tree  
def build() : 
  
    # insert leaf nodes in tree  
    for i in range(N) :  
        tree[n + i] = (float('inf'), float('inf'));  
      
    # build the tree by calculating parents  
    for i in range(n - 1, 0, -1) :  
        tree[i] = min(tree[i << 1], tree[i << 1 | 1])
  
# function to update a tree node  
def updateTreeNode(p, value) :  
      
    # set value at position p  
    tree[p + n] = (value, p);  
    p = p + n;  
      
    # move upward and update parents  
    i = p; 
      
    while i > 1 : 
          
        tree[i >> 1] = min(tree[i], tree[i ^ 1]);  
        i >>= 1;  
  
# function to get sum on interval [l, r)  
def query(l, r) :  
  
    res = (float('inf'), float('inf'));  
      
    # loop to find the sum in the range  
    l += n; 
    r += n; 
      
    while l < r : 
      
        if (l & 1) : 
            res = min(res, tree[l]);  
            l += 1
      
        if (r & 1) : 
            r -= 1; 
            res = min(res, tree[r]);  
              
        l >>= 1; 
        r >>= 1
      
    return res;

par = [None for i in range(N)]
build()
updateTreeNode(0, 0)
for i in range(1, N):
    if s[i] == "1": continue
    r = query(max(0, i - M), i)
    par[i] = r[1]
    updateTreeNode(i, r[0]+1)
    # updateTreeNode(i, query(max(0, i - M), i))
    
    # for k in range(1, M+1):
    #     if i - k < 0: break
    #     dp[i] = min(dp[i], (dp[i-k][0], (i - k)))



moves = []
cur = N - 1
if par[cur] == float('inf') or par[cur] == None:
    print(-1)
    quit()
while par[cur] != None:
    new = par[cur]
    moves.append(cur - new)
    cur = new

moves = list(reversed(moves))
print(" ".join(map(str, moves)))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = list(input())
S = [int(s) for s in S]
S.reverse()
dp = [-1 for i in range(N+1)]
dp[0] = 0
for i in range(1, M+1):
	if i > N:
		break
	if S[i] == 0:
		dp[i] = 1

undetermined = M+1
for i in range(1, N):
	if S[i] == 1:
		undetermined = max(undetermined, i+1)
		continue
	for j in range(undetermined, i+M+1):
		if j <= N
			if S[j] == 0:
				dp[j] = dp[i] + 1
			undetermined = j+1
if dp[N] == -1:
	print(-1)
	exit()

ans = []
prev = (dp[N], N)
for i in range(N-1, -1, -1):
	if dp[i] == -1 or prev[0] == dp[i]:
		continue
	else:
		ans.append(str(prev[1] - i))
		prev = (dp[i], i)

print(" ".join(ans))