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 sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, list(input())[: -1]))
a.reverse()
res = []

table = []
for i in range(N + 1):
  if a[i] == 0: table.append(i)
#print(table)
p = 0
while p < N:
  j = bl(table, p + M)
  q = table[min(len(table) - 1, j)]
  if q > p + M: j -= 1
  q = table[min(len(table) - 1, j)]
  #print(p, q, res)
  if p == q:
    print(-1)
    exit(0)
  res.append(q - p)
  p = q
res.reverse()
print(*res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

m = []
for i, s in enumerate(S):
    if s == '0':
        m.append(i)

cur = 0
output = []
while True:
    i = bisect.bisect_right(m, cur + M)
    
    if i >= len(m):
        output.append(m[i-1] - cur)
        print(' '.join(list(map(str, output[::-1]))))
        break
    elif m[i-1] == cur:
        print(-1)
        break
    
    output.append(m[i-1] - cur)
    cur = m[i-1]

Submission status: Accepted

Solution code:
def main():
    
    n,m = map(int,input().split())
    l = list(input())[::-1]
    ans = []
    i = 0
    l[0] = 0

    while i < n+1:
        if l[i] == 0:
            a = -1
            for j in range(m,0,-1):
                if i+j < n+1 and l[i+j] != "1":
                    a = i+j
                    ans.append(j)
                    l[a] = 0
                    break
            if a == -1:
                print(-1)
                exit()
            else:
                i = a
            
            if l[-1] == 0:
                break
    
    print(*ans[::-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = []

left, right = 0, 0 + m

while True:
    if right >= n:
        ans.append(n - left)
        break
    for i in range(right, left, -1):
        flag = 1
        if s[i] == "0":
            ans.append(i - left)
            flag = 0
            break
    if flag:
        print(-1)
        sys.exit()
    else:
        left = i
        right = left + m

print(*ans[::-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, M = MAP()
	S = input()

	pos_0 = []
	for i in range(N+1):
		if S[i] == "0":
			pos_0.append(i)

	q = deque([])
	pos = N
	while pos != 0:
		next_pos = pos-M
		idx = bisect_left(pos_0,next_pos)
		if pos-pos_0[idx] > M or pos == pos_0[idx]:  # 移動できない
			print(-1)
			exit()

		q.appendleft(pos-pos_0[idx])
		pos = pos_0[idx]

	print(*q)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
S=list(map(int,list(input())))
if m > n:
    m = n
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: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import sys
#input = sys.stdin.readline
from heapq import*


N,M=map(int,input().split())
S=list(input())
S.reverse()
idx=0
lst=[]
while idx<N:
    for i in range(1,M+1)[::-1]:
        if i+idx<=N:
            if S[i+idx]=="0":
                idx+=i
                lst.append(i)
                break

    else:
        print(-1)
        exit()
lst.reverse()
print(" ".join([str(i) for i in lst]))

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    s=input()
    
    route=[]
    i=n
    visited=n
    while True:
        if i-m<=0:
            route.append(i)
            break
        else:
            flag=False
            for j in range(i-m,visited):
                if flag:
                    break
                if s[j]=='0':
                    route.append(i-j)
                    visited=i-m
                    i=j
                    flag=True
            if flag:
                continue
            else:
                print(-1)
                exit()
    
    print(*route[::-1])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    s = input().rstrip()
    ans = []
    x = n
    f = True
    while x > 0 and f:
        for i in reversed(range(m+1)):
            if i == 0:
                f = False
                break
            if s[max(0, x-i)] == '0':
                if x-i < 0:
                    ans.append(x)
                else:
                    ans.append(i)
                x = max(0, x-i)
                break
    if f:
        for v in reversed(ans):
            print(v, end=" ")
        print("")
    else:
        print("-1")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

chk = True
while p<N:
    for i in range(1, min(M, N-p)+1)[::-1]:
        if S[p+i]=="0":
            break
    else:
        print(-1)
        chk = False
        break
    l.append(i)
    p += i

if chk:
    l.reverse()
    print(*l)

Submission status: Accepted

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

ds = []
d = 1
for i in range(1, n+1):
    if s[i] == '0':
        ds.append(d)
        d = 1
    else:
        d += 1
#print(ds)

temp0 = 0
ans = []
for i in range(len(ds)):
    if ds[i] > m:
        print(-1)
        exit()
    temp1 = temp0 + ds[i]
    #print(temp1)
    if temp1 > m:
        ans.append(temp0)
        temp0 = ds[i]
    elif temp1 == m:
        ans.append(temp1)
        temp0 = 0
    else:
        temp0 = temp1
else:
    if temp0 != 0:
        ans.append(temp0)
ans = list(reversed(ans))
print(*ans)

Submission status: Accepted

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

idx = 0
answer = []
flag = False
while True:
    if l - idx > M:
        m = M
    else:
        m = l - idx - 1
        flag = True
    if S[idx + m] == '0':
        answer.append(m)
        idx += m
        if flag:
            break
    else:
        while S[idx + m] == '1':
            m -= 1
            if m == 0:
                print(-1)
                exit()
        answer.append(m)
        idx += m

if answer[-1] == 0:
    answer.pop()
answer = answer[::-1]
print(' '.join(map(str, answer)))

Submission status: Accepted

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

while now<N:
    for i in range(M, 0, -1):
        if now+i>N:
            continue
    
        if S[now+i]=='0':
            ans.append(i)
            now += i
            break
    else:
        print(-1)
        exit()

print(*ans[::-1])

Submission status: Accepted

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

ans = []
i = N
while i>0:
    if i <= M:
        ans.append(i)
        break
    for j in range(M,0,-1):
        if S[i-j]=='1': continue
        ans.append(j)
        i -= j
        break
    else:
        print(-1)
        exit()
print(*ans[::-1])

Submission status: Accepted

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] == "0":
            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))
            break

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

Submission status: Accepted

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

p = N
prev = N
flag = True
ans = []
for i in range(N, -1, -1):
    if (prev - i) > M:
        ans.append(prev - p)
        prev = p
        if (prev - i) > M:
            flag = False
            break
    if S[i] == "0":
        p = i
ans.append(prev)
if flag:
    print(" ".join(map(str, ans[::-1])))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
*s,=map(int,input()[::-1])
i=0
a=[]
while i<n:
    j=min(n,i+m)
    while s[j]:j-=1
    if j==i:
        print(-1)
        exit()
    a+=j-i,
    i=j
print(*a[::-1])

Submission status: Accepted

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

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

while pos > 0:
    dist = dp[pos]
    tmp = pos

    for i in range(1, M + 1):
        if pos - i < 0:
            break
        if S[pos - i] == "0":
            dp[pos - i] = dist + 1
            tmp = pos - i
    if pos == tmp:
        break
    pos = tmp

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

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

print(*ans, sep=" ")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()[::-1]
ans=[]
pos=0
while pos!=n:
  for i in range(min(n-pos,m),0,-1):
    if s[pos+i]=='0':
      ans.append(i)
      pos+=i
      break
  else:
    print(-1)
    exit()
print(*ans[::-1])

Submission status: Accepted

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

ans = []
i = N
while i > 0:
    prev = i
    for j in range(max(0, i-M), i):
        if S[j] == "0":
            ans.append(str(i-j))
            i = j
            break
    if i == prev:
        ans = -1
        break

if ans == -1:
    print(ans)
else:
    ans.reverse()
    print(*ans)

Submission status: Accepted

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

pos = N
step = []
isGoal = 1
while pos > 0:
    for i in range(M, 0, -1):
        if pos - i <= 0:
            step.append(pos)
            pos = 0
        elif S[pos - i] == '0':
            step.append(i)
            pos -= i
        else:
            continue
        break
    else:
        isGoal = 0
        break

if isGoal:
    print(*[x for x in reversed(step)])
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり整数
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

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


now = N
ans = []
while now > 0:
    for step in range(M, 0, -1):
        if now-step <0:
            step = now
        if S[now-step] == "0":
            ans.append(step)
            now -= step
            break
        if step == 1:
            print(-1)
            sys.exit()

ans.reverse()
ret = ""
for a in ans:
    ret+= str(a) + " "

print(ret)

Submission status: Accepted

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

if S[0] == 1 or S[-1] == 1:
    det = -1
else:
    det = 0
    count = 0
    data = []
    for i in range(N+1):
        if S[i] == "0":
            data.append(count+1)
            count = 0
        else:
            count += 1
        if count == M:
            det = -1
            break
    #print(data)
    
if det != -1:
    ans = []
    count = 0
    for i in range(1,len(data)):
        if count + data[i] > M:
            ans.append(count)
            count = data[i]
        else:
            count += data[i]
    ans.append(count)
    ans.reverse()
    print(" ".join(map(str,ans)))

else:
    print(-1)

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    S = input()
    
    ans = []
    check = [False] * (N+1)
    
    idx = N
    while 0 < idx:
        f = False
        for i in range(M, 0, -1):
            if idx-i < 0: continue
            if S[idx-i] == '1':
                if check[idx-i]: print(-1); sys.exit()
                else: check[idx-i] = True
            else:
                ans.append(i)
                idx -= i
                f = True
                break
        if not f: print(-1); sys.exit()
    
    for a in ans[::-1]: print(a)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map( int, input().split())
    S = [ int(s) for s in input()][::-1]
    ANS = []
    t = 0
    while t < N:
        for i in range( min(M, N-t),0,-1):
            if S[t+i] == 0:
                ANS.append(i)
                t += i
                break
        else:
            print(-1)
            return
    if sum(ANS) == N:
        print( " ".join( map( str,ANS[::-1])))
    else:
        print(-1)
                

if __name__ == '__main__':
    main()

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 = sr()
# マスNからスタート
cur = N
answer = []
while cur > 0:
    for x in range(M, 0, -1):
        if cur - x < 0 or S[cur - x] == '1':
            continue
        answer.append(x)
        cur -= x
        break
    else:
        print(-1)
        exit()

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
N, M = map(int, input().split())
s = input()
safe = []
cnt = 0
for i, m in enumerate(s):
  if m=='1':
    cnt += 1
    if cnt==M:
      print(-1)
      break
  else:
    safe += [i]
    cnt = 0
else:
  ps = N
  ans = []
  while ps!=0:
    ind = bisect_left(safe,ps-M)
    ans += [ps-safe[ind]]
    ps = safe[ind]
  print(*ans[::-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left
N, M = map(int, input().split())
s = input()
safe = []
out = []
cnt = 0
for i, m in enumerate(s):
  if m=='1':
    out += [i]
    cnt += 1
    if cnt==M:
      print(-1)
      break
  else:
    safe += [i]
    cnt = 0
else:
  ps = N
  ans = []
  while ps!=0:
    ind = bisect_left(safe,ps-M)
    ans += [ps-safe[ind]]
    ps = safe[ind]
  print(*ans[::-1])

Submission status: Accepted

Solution code:
def main():
    from collections import deque


    INF = float('inf')
    n, m = map(int, input().split())
    s = list(map(int, input()))

    dp = [INF] * (n + 1)
    dp[n] = 0
    queue = deque([0])

    i = n - 1
    while i >= 0:
        while True:
            if not queue:
                print(-1)                
                return            
            if queue[0] != INF and len(queue) <= m:
                break
            queue.popleft()
            
        if s[i] == 0:
            dp[i] = queue[0] + 1
        queue.append(dp[i])
        i -= 1

    ans = []
    v = dp[0]
    num = 0
    for i in dp:
        if i != v and i != INF:
            ans.append(num)
            v = i
            num = 1
        else:
            num += 1

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
s = input()
taboo = '1' * k
for i in range(n-k+1):
  if s[i:i+k] == taboo:
    print(-1)
    break
else:
  s = s[::-1]
  #print(s)
  ans = []
  now = 0
  while True:
    for i in range(k):
      if now + k - i <= n:
        if s[now+k-i] == '0':
          now += k-i
          ans.append(k-i)
          #print(ans)
          break
    if now == n:
      ans.reverse()
      print(' '.join(list(map(str,ans))))
      break

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    s = str(input())
    s = list(reversed(s))
    ans = []
    now = 0
    while now < N:
        for i in reversed(range(min(M,N-now))):
            i += 1
            if s[now+i] == "0":
                now += i
                ans.append(i)
                break
            if i == 1:
                print(-1)
                exit()
        
    print(*reversed(ans))
        
if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = []
right = N

while right > 0:
    left = right
    for i in range(M):
        if S[right-i-1] == '0':
            left = right-i-1
        if left == 0:
            break
    if left == right:
        print(-1)
        break
    ans.append(right-left)
    right = left
else:
    print(*reversed(ans))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
s=s[::-1]
r,l,cnt,k,=0,0,0,0
ans=[]
while 1:
  while cnt<m:
    r+=1
    if r==n:
      ans.append(r-k)
      print(*ans[::-1])
      exit()
    if s[r]=='0':
      l=r
    cnt+=1
  if r-l==m:
    print(-1)
    exit()
  ans.append(l-k)
  k=l
  cnt=r-l

Submission status: Accepted

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

N, M = map(int, input().split())
S = input()
if '1'*M in S:
    print(-1)
    exit()
nums = []
cur = N
min_loc = N
for i in range(N)[::-1]:
    if cur-i > M:
        nums.append(cur-min_loc)
        cur = min_loc
    if S[i] == '0':
        min_loc = min(min_loc, i)
if cur > 0:
    nums.append(cur)
print(' '.join(map(str, nums[::-1])))

Submission status: Accepted

Solution code:
INFTY = 10**6
N,M = map(int,input().split())
S = input().strip()
S0 = []
for i in range(N+1):
    if S[i]=="0":
        S0.append(i)
flag = 0
for i in range(1,len(S0)):
    if S0[i]-S0[i-1]>M:
        flag = 1
        break
if flag==1:
    print(-1)
else:
    C = [[INFTY,-1,-1] for _ in range(N+1)]
    C[N] = [0,0,N]
    cur = N
    curN = -1
    a = 0
    for i in range(len(S0)-2,-1,-1):
        j = S0[i]
        if cur-j<=M:
            pass
        else:
            cur = curN
            a += 1
        C[j] = [a+1,cur-j,cur]
        curN = j
    i = 0
    A = []
    while i<N:
        A.append(C[i][1])
        i = C[i][2]
    print(*A)

Submission status: Accepted

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

c = 0
flag = 0
for i in S:
    if i == '0':
        if c >= M:
            flag = 1
            break
        c = 0
    else:
        c += 1
        
if flag == 1:
    print(-1)
else:
    T = S[::-1]
    now = 0
    ans = []
    while now != N:
        delta = 0
        for i in range(1,M+1):
            if now + i == N:
                delta = i
                break
            if T[now+i] == '0':
                delta = i
        ans.append(delta)
        now += delta
    Answer = ans[::-1]
    print(*Answer)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y
N,M=LI()
S=input()
ptr = N

res = []
while True:
    ok = 0
    for i in range(1,M+1):
        if ptr >= i and S[ptr - i] == '0':
            ok = i
    ptr -= ok
    res.append(ok)
    if ptr == 0:
        res.reverse()
        print(*res)
        exit()
    if ok == 0:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    s = [c == '1' for c in S()]
    r = []
    c = n
    while c > 0:
        nc = -1
        for i in range(min(c,m),0,-1):
            if s[c-i]:
                continue
            r.append(i)
            nc = c - i
            break
        if nc == -1:
            return -1
        c = nc

    return JA(r[::-1], " ")


print(main())

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc145/tasks/abc145_e
#E - All-you-can-eat
"""

"""

N = gi()
M = gi()
S = gw()

lis = [0] * (N + 5)

li = 0

all_good = 1

for i in range(1, N + 1):
    while (i - li > M or (li < i and S[li] == "1")):
        li += 1
    if li == i:
        all_good = 0
        break
    lis[i] = li

if all_good:
    ans = []
    ci = N
    while ci > 0:
        step = ci - lis[ci]
        ans.append(step)
        ci -= step
    ans.reverse()
    for a in ans:
        print(a, end=" ")
else:
    print(-1)

Submission status: Accepted

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


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

    S = S[::-1]
    data = [0]*(N+1)
    past = 0
    for i in range(N+1):
        if S[i] == "1":
            data[i] = past
        else:
            past = i
    ans = []
    curr = 0
    while True:
        ne = curr+M
        if ne >= N:
            ans.append(N-curr)
            break
        if S[ne] == "1":
            ne = data[ne]
            if ne <= curr:
                print(-1)
                return
        ans.append(ne - curr)
        curr = ne
    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: Accepted

Solution code:
import sys
n, m = map(int, input().split())
s = input()
p = n
hist = []
while p>0:
  for i in range(max(0,p-m), p):
    if s[i]=='0':
      hist.append(p-i)
      p = i
      break
  else:
    print(-1)
    sys.exit()
print(*hist[::-1])

Submission status: Accepted

Solution code:
def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        i = 1
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

def examF():
    N, M = LI()
    S = SI()
    ans = []
    cur = N
    while(cur>0):
        k = min(M,cur)
        while(S[cur-k]=="1"):
            k -=1
            if k==0:
                print("-1")
                return
        ans.append(k)
        cur -=k
    for v in ans[::-1]:
        print(v)
    return


import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examF()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, S: int):
    cur = N
    ret = []
    while cur - M > 0:
        found = False
        t = -1
        for i in range(M, 0, -1):
            if S[cur - i] == '0':
                t = i
                break
        if t > 0:
            cur -= t
            ret.append(t)
        else:
            print(-1)
            return
    ret.append(cur)
    ret.reverse()
    ret = ' '.join([str(r) for r in ret])
    print(ret)
    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: int
    solve(N, M, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

steps = [[] for i in range(N+1)]
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: Accepted

Solution code:
n, m = map(int, input().split())
s = list(input())
s = s[::-1]
ans_list = []

for i in range(n+1):
    if i == 0:
        tmp_count = 0
        tmp_ans = 0
    else:
        tmp_count += 1
        if s[i] == '0':
            tmp_ans = tmp_count
        if tmp_count == m:
            ans_list.append(tmp_ans)
            tmp_count -= tmp_ans
            tmp_ans = tmp_count

if 1 <= tmp_ans <= m:
    ans_list.append(tmp_ans)
if ans_list.count(0) >= 1:
    ans_list = [-1]
    
for i in range(len(ans_list)):
    ans_list[i] = str(ans_list[i])
ans_list = ans_list[::-1]
print(' '.join(ans_list))

Submission status: Accepted

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