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: Accepted

Solution code:
import bisect

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

ok = True
cnt = 0
for c in S:
    if c == "1":
        cnt += 1
        if cnt == M:
            ok = False
            break
    else:
        cnt = 0

# 後ろから見て、各マスからもっとも近い右側の0の位置を格納(S[i]=0ならi)
ngo_pos = [0 for _ in range(N+1)]
most_neighbor_zero_pos = N
for i in range(N, -1, -1):
    if S[i] == "0":
        ngo_pos[i] = i
        most_neighbor_zero_pos = i
    else:
        ngo_pos[i] = most_neighbor_zero_pos

if not ok:
    print(-1)
else:
    ans = []
    pos = N
    while pos > 0:
        npos = ngo_pos[max(0, pos-M)]
        ans.append(pos-npos)
        pos = npos
    print(" ".join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
S = input()
tmp = 0
for i in range(N+1):
	if S[i] == '1':
		tmp += 1
		if tmp == M:
			print(-1)
			sys.exit()
	else:
		tmp = 0

ans = []

i = N
while i > M:
	ind = S[i-M:i].find('0')
	ans.append(M-ind)
	i -= M - ind

ans.append(i)

print(*ans[::-1])

Submission status: Accepted

Solution code:
import sys

#+++++

def main():
	n, m = map(int, input().split())
	s=input()
	s=s[::-1]
	#arch=[len(s)+100]*len(s)
	
	pos=0
	ret=[]
	while pos < len(s)-1:
		for mi in range(m,0,-1):
			if pos+mi >= len(s):
				pass
			elif s[pos+mi]=='0':
				pos += mi
				ret.append(mi)
				#print(pos)
				break
			else:
				pass
		else:
			return -1
	
	r=ret[::-1]
	print(*r)
	
'''
def main2():
	n, m = map(int, input().split())
	s = input()
	
	tt=[-1]*len(s)
	t_parent=[-1]*len(s)
	rs=s[::-1]
	open_list=[0]
	max_dist = 0
　	while True#len(open_list) > 0:
		st, parent, count = open_list.pop()
		for i in range(m, 0, -1):
			aa = st + i
			if aa > n+1:
				pass
			
			#gmマス
			if rs[aa] == 1:
				continue
			
			#アクセス済み
			if tt[aa] > 0:
				break
				
			tt[aa] = count+1
			t_parent[aa] = st
			open_list.append(aa, st, count+1)
			
	print(1)
'''
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

if "1" * m in s:
    print(-1)
    exit()

pos = n
ans = []
while pos > 0:
    prev = max(pos - m, 0)
    while s[prev] == "1":
        prev += 1

    ans.append(pos - prev)

    pos = prev

ans = ans[::-1]
print(*ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
t=list(input().rstrip())
s=[]
for i in range(n+1):
    s.append(int(t[n-i]))
ans=[]
now=0
while now<n:
    for i in range(m,0,-1):
        if now+i<=n:
            if s[now+i]==0:
                ans.append(i)
                now=now+i
                break
    else:
        print(-1)
        sys.exit()
ans.reverse()
for i in ans:
    print(i,end='')
    print(' ',end='')

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

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

    def isOK(index):
        return S[index] == "0"
    
    ans = []
    now = N
    while now:
        for step in range(min(now, M), -1, -1):
            if step == 0:
                print(-1)
                exit()

            if isOK(now-step):
                ans.append(step)
                now -= step
                break
    print(*ans[::-1], sep=" ")



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,m = get_nums_l()
s = input()
s = s[::-1]

now = 0
steps = []
while now < n:
    for i in range(m,0,-1):
        if now+i > n:
            continue
        if s[now+i] == "0":
            now += i
            steps.append(i)
            break
    else:
        print(-1)
        exit()

print(" ".join(map(str, reversed(steps))))

Submission status: Accepted

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

cur = n
while cur > m:
  for a in range(m):
    if s[cur - m + a] == '0':
      roulette.append(m - a)
      cur = cur - m + a
      break
  else:
    print(-1)
    break
else:
  roulette.append(cur)
  print(' '.join(map(str, roulette[::-1])))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
S = input()
ans = []
cur = n
temp = 0
flag = True
while cur != 0:
    kouho = 0
    for i in range(1,m+1):
        if cur-i >= 0:
            if S[cur-i] == '0':
                kouho = max(kouho, i)
    if kouho == 0:
        flag = False
        break
    else:
        ans.append(kouho)
        cur = cur-kouho
if flag:
    ans.reverse()
    print(' '.join(map(str, ans)))
else:
    print(-1)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
s = input()

s = s[::-1]

ans = []
ima = 0
while ima != n:
    flag = False
    for i in range(m):
        tmp = m - i
        if ima + tmp > n:
            continue
        elif s[ima+tmp] ==str(1):
            continue
        else:
            ima += tmp
            ans.append(tmp)
            flag = True
            break
    if flag == False:
        print(-1)
        exit()  

print(*ans[::-1])

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 146
# F - Sugoroku
# https://atcoder.jp/contests/abc146/tasks/abc146_f
import sys
N, M = map(int, input().split())
*S, = map(int, input())
S.reverse()

i = 0
ans = []
while i < N:
    for m in range(M, 0, -1):
        if i+m <= N and S[i+m] == 0:
            i += m
            ans += [m]
            break
    else:
        print(-1)
        sys.exit()

print(*ans[::-1])

Submission status: Accepted

Solution code:
N,M = map(int,(input().split()))
s = list(input())
s.reverse()
now = 0
me = []
flag = 0

while now != N:
    for i in range(1,M+1,)[::-1]:
        if now + i <= N  and  s[now+i] == "0":
            now += i
            me.append(i)
            break
    else:
        print(-1)
        flag = 1
        break

if flag == 0:
    me.reverse()
    print(*me)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(input())
for i in range(len(S)):
    S[i] = int(S[i])
S.reverse()
ans = []
cnt = 0
flag = True
i = 0
while i < N:
    for j in range(0,min(M, N-i)):
        if S[i+min(M,N-i)-j] == 0:
            ans.append(min(M,N-i)-j)
            i += min(M,N-i)-j
            break
    else:
        flag = False
        break
    continue
ans.reverse()
if flag:
    print(*ans)
else:
    print(-1)

Submission status: Accepted

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

now = n
ans_rev = []
while(now != 0):
    for i in range( max(0,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: Accepted

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

s_0 = []
for i in range(n+1):
    if(s[i] == '0'):
        s_0.append(i)

# 二分木
import bisect

now = n
ans_rev = []
while(now != 0):
    next_i = bisect.bisect_left(s_0, now-m)
    next = s_0[next_i]
    if(now == next):
        print(-1)
        exit()
    ans_rev.append(now-next)
    now = next

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
n += 1
s = input()
dst = [float("inf")]*n
dst[-1] = 0
m_last = n-1

for i in reversed(range(n-1)):
    if s[i] == "1":
        continue
    for j in reversed(range(min(m_last+1, i+m+1))):
        # print(i, j)
        if s[j] == "0":
            dst[i] = dst[j]+1
            m_last = j
            break

    if dst[i] == float("inf"):
        print(-1)
        exit()

# print(dst)
last_idx = 0
last_num = dst[0]
ans = []
for i in range(1, n):
    if dst[i] != float("inf") and dst[i] != last_num:
        ans.append(i - last_idx)
        last_num = dst[i]
        last_idx = i

print(*ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N, M = map(int, input().split())
    S = input()[:-1][::-1]
    # print(S)

    res = []
    n = 0
    while n < N:
        miss = True
        for m in reversed(range(1,M+1)):
            if n+m < N+1 and S[n+m] == "0":
                n += m
                res.append(str(m))
                miss = False
                break
        if miss:
            print(-1)
            return
        
    print(" ".join(reversed(res)))

    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    s = input()
    ss = s[::-1]
    if n <= m:
        print(n)
    else:
        cnt = 0
        for i in range(n + 1):
            if s[i] == "1":
                cnt += 1
            else:
                cnt = 0
            if cnt >= m:
                print(-1)
                exit()
        pos = 0
        res = []
        while n != pos:
            for i in reversed(range(m + 1)):
                if pos + i > n:
                    continue
                if ss[pos + i] != "1":
                    pos += i
                    res.append(i)
                    break
        print(*res[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
S=S[::-1]
count=0
count_1=0
count_2=0
answer=[]
ans=0

for i,s in enumerate(S):
    #print(i)
    if i==0:
        pass
    elif i==N:
        count_1+=1
        answer.append(count_1)
        #print("g")
    elif s=="0"and count_1<M-1:
        count_1+=1
        count=count_1
        count_2=0
        #print("a")
    elif s=="0" and count_1==(M-1):
        count_1+=1
        count_2=0
        answer.append(count_1)
        count=0
        count_1=count
        #print("b")
    else:
        if count_1<M-1 and count_2<M-1:
            count_1+=1
            count_2+=1
            #print("c")
        elif count_2==M-1:
            ans=-1
            #print("d")
            break
        elif count_1==M-1:
            count_2+=1
            answer.append(count)
            count_1=count_2
            count=count_1
            #print("e")
if ans==-1:
    print(-1)
else:
    print(" ".join(map(str,answer[::-1])))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input()
ans = []
tmp = S[::-1]
index = 0
acnt = M
while True:
    if acnt == 0:
        print(-1)
        exit()
    if index + acnt <= N and tmp[index + acnt] == '0':
        ans.append(acnt)
        index += acnt
        acnt = M
    else:
        acnt -= 1
    if index == N:
        break
print(*reversed(ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = list(input())[::-1]
i = 0
ans = 0
ans_list = []
while i < n:
    l = s[i+1:i+m+1]
    for next in range(m-1, -2, -1):
        if next == -1:
            print(-1)
            exit()
        if next > len(l)-1:
            continue
        if l[next] == '0':
            ans_list.append(next+1)
            i += next+1
            break
print(' '.join(map(str, ans_list[::-1])))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, m = MAP()
s = STR()
ans = []
i = n
while i > 0:
    if s[i] == '0':
        prei = i
        for j in reversed(range(1, m + 1)):
            if i - j >= 0 and s[i - j] == '0':
                ans.append(str(j))
                i -= j
                break
        if i == prei:
            print(-1)
            exit()
ans.reverse()
print(' '.join(ans))

Submission status: Accepted

Solution code:
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する。
    built(array)   := arrayを初期値とするセグメント木を構築する O(N)。
    update(i, val) := i番目の要素をvalに変更する。
    get_val(l, r)  := 区間[l, r)に対する二項演算の畳み込みの結果を返す。
    """
    def __init__(self, n, op, e):
        """要素数、二項演算、単位元を引数として渡す
        例) 区間最小値 SegmentTree(n, min, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築する"""
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        """i番目の要素をvalに変更する"""
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res_l, res_r = self.e, self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.node[r], res_r)
            l, r = l >> 1, r >> 1
        return self.op(res_l, res_r)

n, m = map(int, input().split())
s = input()
INF = 10 ** 18

st = SegmentTree(n + 1, min, INF)
st.update(n, 0)

for i in range(n)[::-1]:
    if s[i] == "1":
        continue
    tmp = st.get_val(i + 1, min(i + 1 + m, n + 1)) + 1
    st.update(i, tmp)

if st.get_val(0, 1) >= INF:
    print(-1)
    exit()

ans = []
ind = 0
for i in range(n + 1):
    if st.get_val(ind, ind + 1) - 1 == st.get_val(i, i + 1):
        ans.append(i - ind)
        ind = i
print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
s = input()


inf=float("inf")
#i番目のマスに行くための最小手数と、なんマス移動してきたか
dp = [(0,0)] + [(inf,None) for _ in range(n)]
for i in range(1,n+1):
    if s[i]=="0":
        for j in range(min(m,i),0,-1):
            if dp[i-j][0]<inf:
                dp[i]=(dp[i-j][0]+1,j)
                break
if dp[-1][1]:
    i = n
    ret = []
    ra = ret.append
    while dp[i][1]:
        ra(dp[i][1])
        i-=dp[i][1]
    print(" ".join(map(str,ret[::-1])))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    inf=10**9
    n,m=MI()
    s=SI()
    dp=[inf]*(n+1)
    dp[0]=0
    pre=[-1]*(n+1)
    q=deque()
    q.append((0,0))
    for i,c in enumerate(s[1:]):
        if q[0][0]==i-m:q.popleft()
        if c=="0":
            dp[i+1]=q[0][1]+1
            pre[i+1]=q[0][0]
        while q and q[-1][1]>dp[i+1]:q.pop()
        q.append((i+1,dp[i+1]))
    if dp[-1]>=inf:print(-1)
    else:
        ans=[]
        now=n
        while n:
            ans.append(n-pre[n])
            n=pre[n]
        print(*ans[::-1])

main()

Submission status: Accepted

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

cnt,cnt1 = 0,0
for s in S:
    if s == "1":
        cnt1 += 1
    else:
        cnt = max(cnt, cnt1)
        cnt1 = 0
if cnt >= M:
    print(-1)
    exit()

ans = []
pos = N
while pos > 0:
    for m in range(M, 0, -1):
        if pos - m < 0: continue
        if S[pos - m] == "1": continue

        ans.append(m)
        pos -= m
        break

print(*ans[::-1])

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
S = [int(c) for c in input()][::-1]

c = 0
path = []
while c < N:
    g = c+M if c+M < N else N
    for m in range(g, c, -1):
        if S[m] == 1:
            continue
        else:
            path.append(m-c)
            c = m
            break
    else:
        if c < N:
            print(-1)
            sys.exit()

print(*path[::-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = input()
dp = [0]*(n+1)
r = n

for i in range(n-1,-1,-1):
    if int(s[i]) == 1:
        dp[i] = -1
        continue
    while r > i+m:r-=1
    while dp[r] == -1:r -= 1
    if r == i:
        print(-1)
        exit(0)
    dp[i] = dp[r]+1
now = 0
ans = []
for i in range(n+1):
    if dp[i] == -1:continue
    if dp[i] != dp[now]:
        ans.append(i-now)
        now = i
print(*ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, list(input())))
dp = [-1]*(n+1)
te = [-1]*(n+1)
te[n] = 0
g = [n]
c = 0
r = n
for i in reversed(range(n)):
  if a[i]:
    continue
  if i + m < r:
    r = i + m
    while a[r]:
      r -= 1
    if r == i:
      print(-1)
      exit(0)
  dp[i] = r
  te[i] = te[r] + 1
  if c < te[i]:
    c += 1
    g.append(i)
  g[te[i]] = i
g = g[::-1]
d = [y - x for x, y in zip(g,g[1:])]
print(*d)

Submission status: Accepted

Solution code:
from itertools import accumulate

N, M = map(int, input().split())
S = list(map(int, input()))
cum = list(accumulate([0] + S))
ok = [False] * (N+1)
for i in range(N):
    if S[i] == 0 and cum[i+1] - cum[max(0, i-M+1)] < min(i+1, M):
        ok[i] = True
s = N
t = N
i = N
ans = []
while t > 0:
    if s - i > M:
        if s == t:
            print(-1)
            exit()
        ans.append(s - t)
        s = t
        i = s
        continue
    if ok[i]:
        t = i
    i -= 1
ans.append(s)
print(*ans[::-1])

Submission status: Accepted

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

pos = [n - 1]
ind = n - 1
while True:
    tmp = -1
    for i in range(1, m + 1):
        if s[max(ind - i, 0)] == "0":
            tmp = max(ind - i, 0)
    if tmp == -1:
        print(-1)
        exit()
    pos.append(tmp)
    ind = tmp
    if ind == 0:
        break
tmp = pos[::-1]
ans = []
for i in range(len(tmp) - 1):
    ans.append(tmp[i + 1] - tmp[i])
print(*ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    s = list(map(int, input()))
    d = [float("inf")]*(n+1)
    d[n] = 0
    i = n
    p = n
    while i:
        nd = d[i]+1
        for j in range(1,min(i,m)+1):
            k = p-j
            if not s[k]:
                d[k] = nd
                i = k
        if i == p:
            print(-1)
            return
        p = i
    ans = []
    l = 0
    while l < n:
        for i in range(1,min(m,n-l)+1):
            if d[l+i] < d[l]:
                l += i
                ans.append(i)
                break
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = input().strip("\n")
    now = N
    ans = []
    while now > 0:
        for i in reversed(range(1, M+1)):
            if now - i < 0: continue
            elif S[now - i] == "0":
                ans.append(i)
                now -= i
                break
        else: 
            print(-1)
            break
    else: 
        A = [int(ans[-1 - i]) for i in range(len(ans))]
        print(" ".join(map(str, A)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
s = input().rstrip()
s_rev = s[::-1]

place = 0

ans = []

while place < n:
    flag = 1
    for i in range(min(m, n - place), 0, -1):
        if s_rev[place + i] == "0":
            ans.append(i)
            place += i
            flag = 0
            break
    if flag:
        print(-1)
        sys.exit()

print(*ans[::-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=list(input())
s.reverse()
ansl=[]
now=0
while now<n:
    f=1
    for i in range(m,0,-1):
        if now+i<n+1 and s[now+i]=="0":
            ansl.append(i)
            now+=i
            f=0
            break
    if f:
        print(-1)
        exit()


ansl.reverse()
print(*ansl)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
s = list(input())[::-1]
res = []
now = 0
while now != n:
    nex = min(now + m, n)
    while s[nex] == '1':
        nex -= 1
        if nex == now:
            print(-1)
            quit()
    res += [nex - now]
    now = nex
print(*res[::-1])

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    S = input()
    from itertools import groupby
    for k, v in groupby(S):
        if k == '1' and len(list(v)) >= M:
            return print(-1)

    ans = []
    i = 0
    S = S[::-1]
    while i <= N:
        cur = M
        while N < i+cur or S[i+cur] == '1':
            cur -= 1
        i += cur
        if cur == 0:
            break
        ans.append(cur)

    ans = ans[::-1]
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

N, M = map(int, input().split())
S = [N - i for i, s in enumerate(input()) if s == '0']
S = S[::-1]

ans = []
now = 0
while now < N:
    i = bisect_right(S, now + M) - 1

    if S[i] == now:
        print('-1')
        exit()

    ans.append(S[i] - now)
    now = S[i]

print(*ans[::-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
S = list(map(int, input()))[::-1]
L = []
now = 0
while now < n:
  if n - now <= m:
    L.append(n - now)
    break
  for i in range(m, 0, -1):
    if not S[now+i]:
      now += i
      L.append(i)
      break
  else:
    print(-1)
    exit()
print(*L[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
S = list(sr())[::-1]
answer = []
count = 0
cur = 0
while True:
    next = cur
    for i in range(M, 0, -1):
        if cur + i > N:
            continue
        if S[cur+i] == '0':
            count += 1
            next = cur + i
            answer.append(i)
            break
        else:
            continue
    if next == cur:
        print(-1); exit()
    cur = next
    if next == N:
        break

answer = answer[::-1]
print(*answer)

Submission status: Accepted

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

l = []
cur = n

while cur > 0:
  position = cur
  cur = max(0, cur - m)
  while s[cur] == "1":
    cur += 1
  if cur == position:
    print(-1)
    exit(0)
  l.append(str(position - cur))
l.reverse()
print(" ".join(l))

Submission status: Accepted

Solution code:
#146_F
n, m = map(int, input().split())
s = input()[::-1]
ans = []

flg = True
cur = 0
while cur < n and flg:
    for to in range(cur + m, cur, -1):
        if to > n:
            continue
            
        if s[to] == '0':
            ans.append(to - cur)
            cur = to
            break
        
        if to == cur + 1:
            flg = False

if flg:
    print(*ans[::-1])
else:
    print(-1)

Submission status: Accepted

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

load=[S[-i-1] for i in range(0,N+1)]


near=[-1 for i in range(0,N+1)]
log=0
for i in range(0,N+1):
    if load[i]=='0':
        near[i]=i
        log=i
    else:
        near[i]=log

ans=[]
start=0
while start<N:
    if N>start+M:
        next=near[start+M]
        if start>=next:
            print(-1)
            break
        ans.append(next-start)
        start=next
    else:
        ans.append(N-start)
        start=N
else:
    ans=ans[::-1]
    print(*ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
ans = []
hr = n
while hr > 0:
    for i in reversed(range(1, m + 1)):
        if 0 <= hr - i <= n and s[hr - i] == 0:
            ans.append(i)
            hr -= i
            break
ans = list(reversed(ans))
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(' '.join(ans))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = input()
cnt = [0]*(n+1)
r = n
for i in range(n-1,-1,-1):
    if s[i] == '1':
        cnt[i] = -1
        continue
    while r > i+m:r -=1
    while cnt[r] == -1:r -= 1
    if i == r:
        print(-1)
        exit(0)
    cnt[i] =cnt[r]+1
now = 0
ans = []
for i in range(n+1):
    if cnt[i] == -1:continue
    if cnt[i] == cnt[now]-1:
        ans.append(i-now)
        now = i
print(*ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = list(input())
s.reverse()
for i in range(m):
    s.append("1")
p = 0
ans = []
while p < n:
    p += m
    cnt = m
    while s[p] == "1":
        p -= 1
        cnt -= 1
        if cnt == 0:
            print(-1)
            exit()
    ans.append(cnt)
ans.reverse()
print(*ans)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    S = input()
    from itertools import groupby
    for k, v in groupby(S):
        if k == "1" and M <= len(list(v)):
            return print(-1)
    ans = []
    posi = 0
    S = S[::-1]
    while posi < N:
        pre = posi
        posi = min(posi+M, N)
        while S[posi] == "1":
            posi -= 1
        ans.append(posi - pre)
    print(*(ans[::-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right

N, M = map(int, input().split())
S = [-i for i, s in enumerate(input()) if s == '0']
S = S[:: -1]

ans = []
now = 0
while S[now] != 0:
    to = bisect_right(S, S[now] + M) - 1

    if to == now:
        print('-1')
        exit()
    ans.append(S[to] - S[now])
    now = to

ans = ans[:: -1]
print(*ans)