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
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    s = list(input())

    ans = []

    idx = n
    while idx != 0:
        exitFlg = True
        for i in range(min(idx, m), 0, -1):
            if s[idx - i] == "0":
                idx -= i
                ans.append(i)
                exitFlg=False
                break

        if exitFlg:
            print(-1)
            exit(0)

    ans.reverse()
    print(*ans, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    S = S[::-1]
    idx = 0
    ans = []
    while idx < N:
        step = 0
        for i in range(min(M, N - idx), 0, -1):
            if S[idx + i] == '0':
                step = i
                break
        if step == 0:
            print(-1)
            return
        ans.append(step)
        idx += step

    print(*reversed(ans))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    S = S[::-1]
    idx = 0
    ans = []
    while idx < N:
        step = 0
        for i in range(1, M + 1):
            if S[idx + i] == '0':
                step = i
            if idx + i == N:
                break
        if step == 0:
            print(-1)
            return
        ans.append(step)
        idx += step

    print(*reversed(ans))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
    
n,m = map(int,input().split())
s = input()
lis = []
now = len(s)-1
ju = 0
ju2 = 0
while now>0:
    ju = 0
    if ju2==1:
        break
    for i in range(m,0,-1):
        if now-i<0:
            continue
        if now-i ==0:
            lis.append(i)
            ju = 1
            now = 0
            break
        if s[now-i]=="0":
            now = now-i
            lis.append(i)
            ju = 1
            break
        if i==1 and ju==0:
            ju2 = 1
            break
if ju2==0:
    lis.reverse()
    print(*lis)
else:
    print(-1)

Submission status: Accepted

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

  c,l=N,[]
  while c>0:
    for i in range(M,0,-1):
      if i<=c and S[c-i]=='0':
        l+=[i]
        c-=i
        break
    else:
      l=[-1]
      break
  print(*l[::-1])

main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
n += 1
s = list(input())
dp = [0] * n
for i in range(1, n):
    if i - m < 0 and s[n - i - 1] == "0":
        dp[i] = 1
    elif s[n - i - 1] == "1":
        dp[i] = -1
    else:
        for j in range(i - m, i):
            if not dp[j] == -1:
                dp[i] = dp[j] + 1
                break
t = [0] * n
j = 0
x = dp[n - 1] + 1
for i in range(n - 1, -1, -1):
    if dp[i] == x - 1:
        t[j] = i
        j += 1
        x -= 1
    elif dp[i] == 0:
        print(-1)
        exit()
ans = [t[i] - t[i + 1] for i in range(j - 1)]
print(*ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    S = input().strip()

    if S.count("1" * M) > 0:
        print(-1)
        return

    ans = []
    r = N
    while r > 0:
        li = N - 1
        for diff in range(1, M + 1):
            if r - diff < 0:
                break
            if S[r - diff] == "0":
                li = r - diff
        ans.append(r - li)
        r = li
        if r == 0:
            break

    ans.reverse()
    print(*ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

#↓s      g↓
#0001000100
#0123456789
# x  x x   

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

ans=[]
i=0
while i < n:
    best=min(i+m,n)
    flag=0
    while best>i:

        if s[best]=="0":
            ans.append(str(best-i))
            i=best
            flag=1
        else:
            best-=1


    if flag==0:
        print(-1)
        exit()

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

Submission status: Accepted

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

ans = []

now_pos = N

while now_pos > 0:
    next_pos = max(0, now_pos - M)
    for i in range(M):
        if S[next_pos + i] == "0":
            ans.append(now_pos - (next_pos + i))
            now_pos = next_pos + i
            break
    else:
        print(-1)
        exit()

print(" ".join(map(str, ans[::-1])))

Submission status: Accepted

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

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

print(*reversed(ans))

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
slist=list(map(int,input()))

seq=0
for s in slist:
  if s==0:
    seq=0
  else:
    seq+=1
    if seq==M:
      print(-1)
      sys.exit(0)

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)      
  def update(self, k, x):
    #k番目の値をxに更新
    #k: index(0-index)
    #x: update value
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  def query(self, l, r):
    #[l, r)のsegfuncしたものを得る
    #l: index(0-index)
    #r: index(0-index)
    res = self.ide_ele
    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res

#segfunc
def segfunc(x,y):
  return min(x,y) #最小値
#ide_ele
ide_ele=float("inf") #最小値
#init
seg=SegTree([float("inf")]*(N+1), segfunc, ide_ele)

dist_list=[float("inf")]*(N+1)
seg.update(N,0)
dist_list[N]=0
for i in reversed(range(N)):
  if slist[i]==0:
    left=i+1
    right=min(i+M,N)
    dist=seg.query(left,right+1)+1
    seg.update(i,dist)
    dist_list[i]=dist

answer_list=[]
i=0
while i<N:
  for j in range(1,M+1):
    if dist_list[i]>dist_list[i+j]:
      answer_list.append(j)
      i+=j
      break
    
print(*answer_list)

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
slist=list(map(int,input()))

seq=0
for s in slist:
  if s==0:
    seq=0
  else:
    seq+=1
    if seq==M:
      print(-1)
      sys.exit(0)

#####segfunc#####
def segfunc(x,y):
  return min(x,y)

#####ide_ele#####
ide_ele=float("inf")

class SegTree:
  """
  init(init_val, ide_ele): 配列init_valで初期化 O(N)
  update(k, x): k番目の値をxに更新 O(logN)
  query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  """
  def __init__(self, init_val, segfunc, ide_ele):
    """
    init_val: 配列の初期値
    segfunc: 区間にしたい操作
    ide_ele: 単位元
    n: 要素数
    num: n以上の最小の2のべき乗
    tree: セグメント木(1-index)
    """
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  def update(self, k, x):
    """
    k番目の値をxに更新
    k: index(0-index)
    x: update value
    """
    k += self.num
    self.tree[k] = x
    while k > 1:
      self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
      k >>= 1

  def query(self, l, r):
    """
    [l, r)のsegfuncしたものを得る
    l: index(0-index)
    r: index(0-index)
    """
    res = self.ide_ele

    l += self.num
    r += self.num
    while l < r:
      if l & 1:
        res = self.segfunc(res, self.tree[l])
        l += 1
      if r & 1:
        res = self.segfunc(res, self.tree[r - 1])
      l >>= 1
      r >>= 1
    return res
  
seg=SegTree([float("inf")]*(N+1), segfunc, ide_ele)
seg.update(N,0)

for i in reversed(range(N)):
  if slist[i]==0:
    left=i+1
    right=min(i+M,N)
    seg.update(i,seg.query(left,right+1)+1)

dist_list=[]
for i in range(N+1):
  dist_list.append(seg.query(i,i+1))
#print(dist_list)

answer_list=[]
i=0
while i<N:
  for j in range(1,M+1):
    if dist_list[i]>dist_list[i+j]:
      answer_list.append(j)
      i+=j
      break
    
print(*answer_list)

Submission status: Accepted

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

cnt = 0
pos = 0
tmp = 0
lst = []
while pos != n:
    pos += 1
    cnt += 1
    if cnt == m:
        if sugoroku[pos] == "0":
            lst.append(cnt)
            cnt = 0
        else:
            if tmp == 0:
                print(-1)
                exit()
            lst.append(tmp)
            cnt -= tmp
            tmp = 0
    else:
        if sugoroku[pos] == "0":
            tmp = cnt
if cnt != 0:
    lst.append(cnt)
for num in lst[::-1]:
    print(num, end = " ")

Submission status: Accepted

Solution code:
from bisect import *
n, m = map(int, input().split())
s = input()

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

now = n
ans = [n]

while now > 0:
    next = masu[bisect_left(masu, now-m)]
    if now != next:
        ans.append(next)
        now = next
    else:
        ans = -1
        break

if ans == -1:
    print(-1)

else:
    ans.reverse()
    for i in range(len(ans)-1):
        print(ans[i+1]-ans[i])

Submission status: Accepted

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

#まず何手でクリアできるかを把握する
count = 1
inf = 10**10

#ゴールまでその地点から何手で到達できるかを記録する
length = [inf]*(n+1)
length[0] = 0
now = 0
flag = True

while flag:
    ok = 0
    for i in range(1,m+1):
        if s[now+i] == "1":
            continue
        length[now+i] = count
        ok = now+i
        if now+i == n:
            flag = False
            break
    if ok == 0:
        print(-1)
        exit()
    now = ok
    count += 1

count -= 2

#スタートからの軌跡を格納するリスト
li = []
length = length[::-1]
point = 0

for i,j in enumerate(length):
    if j == count:
        count -= 1
        li.append(point)
        point = 0
    point += 1

print(*li)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
s = input()
c = n
ans = []
while True:
    p = None
    for i in range(1,m+1):
        if c-i>=0 and s[c-i]=="0":
            p = i
    if p is None:
        ans = -1
        break
    c -= p
    ans.append(p)
    if c==0:
        break
if ans==-1:
    print(ans)
else:
    write(" ".join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()[::-1]
ans=[]
now=0
while n>m-1:
  x=s[now+1:now+m+1][::-1]
  memo=x.find('0')
  if memo<0:
    print(-1)
    quit()
  n-=(m-memo)
  now+=(m-memo)
  ans.append(str(m-memo))
if n>0:
  ans.append(str(n))
print(' '.join(ans[::-1]))

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    s = input()[::-1]
    ni = 0
    me = []
    while ni < n:
        for i in range(m):
            if ni+m-i <= n and s[ni+m-i] == "0":
                ni = ni+m-i
                me.append(str(m-i))
                break
            if i == m-1:
                print(-1)
                exit()
    print(" ".join(me[::-1]))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
S=input()
now=S[N-1]
dp=[float("INF")]*(N+1)
dp[N]=0
nowmin=0
right=N
for left in range(N-1,-1,-1):
    while right-left>M or S[right]=="1":
        right-=1
        nowmin=dp[right]
    if right<=left:
        print(-1)
        exit()
    if S[left]=="1":
        continue
    else:
        dp[left]=1+nowmin
#print(dp)
#print(dp[0])
now=dp[0]
nowi=0
"""
if now==float("INF"):
    print(-1)
    exit()
"""
for i in range(1,N+1):
    if now>dp[i]:
        print(i-nowi, end=" ")
        now=dp[i]
        nowi=i

Submission status: Accepted

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

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

p = -1
for i in reversed(range(1,M+1)):
    if S[i] == "0":
        p = i
        break

if p == -1:
    print(-1)
    exit()

ps = [p]
while 1:
    tmp = -1
    for i in reversed(range(ps[-1]+1,ps[-1]+M+1)):
        try:
            if S[i] == "0" or i == N:
                ps.append(i)
                tmp = i
                break
        except:
            pass
    if tmp == -1:
        print(-1)
        exit()
    if ps[-1] == N:
        break

pp = ([ps[i+1]-ps[i] for i in range(len(ps)-1)])[::-1] + [ps[0]]
print(*pp)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input()
prev = N
pos = N
ans = []
while pos > 0:
    for i in range(M, 0, -1):
        if pos - i >= 0 and S[pos - i] == '0':
            ans.append(i)
            pos -= i
            break
    if pos == prev:
        ans = [-1]
        break
    prev = pos
print(*ans[::-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input()
pos = N
ans = []
while pos > 0:
    for i in range(M, 0, -1):
        if pos - i < 0 or S[pos - i] == '1':
            continue
        ans.append(i)
        pos -= i
        break
    else:
        ans = [-1]
        break
print(*ans[::-1])

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    s=readline().strip()

    ans=[]
    flag=False
    i=n
    while True:
        max_i=i
        for sa in range(1,m+1):
            if i-sa==0:
                ans.append(sa)
                flag=True
                break
            else:
                if s[i-sa]=="0":
                    max_i=i-sa
        if flag: break
        else:
            if max_i!=i:
                ans.append(i-max_i)
                i=max_i
            else:
                break

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = input().strip("\n")
    ans = deque()
    current = N
    while current > 0:
        for i in reversed(range(1, M+1)):
            if current - i >= 0 and S[current - i] == "0":
                ans.appendleft(i)
                current -= i
                break
        else: break
    if current > 0: print(-1)
    else: print(*ans, sep=" ")


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

ans = []
now = N
while now > 0:
    nxI = bisect_left(S, now - M)
    nx = S[nxI]

    if nx == now:
        print(-1)
        exit()

    ans.append(now - nx)
    now = nx

print(*ans[::-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
ans=[]
cursor=n
actualfail=0
while cursor!=0:
  if cursor<=m:
    ans.append(cursor)
    break
  failflag=1
  for i in range(m):
    if s[cursor-m+i]=='0':
      failflag=0
      ans.append(m-i)
      cursor-=m-i
      break
  if failflag==1:
    actualfail=1
    break
if actualfail==1:
  print(-1)
else:
  ans.reverse()
  for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#!python3

from collections import deque

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
S = input()

INF = 10 ** 6


def main():
    w = [(INF, INF)] * (N + 1)
    w[0] = (0, 0)
    # (cost, index)
    dq = deque([(0, 0)])
    for i in range(1, N + 1):
        if i - dq[0][1] > M:
            dq.popleft()
        if len(dq) == 0:
            print(-1)
            return
        if S[i] == "0":
            w[i] = (dq[0][0] + 1, i - dq[0][1])
            dq.append((w[i][0], i))

    ans = []
    x = N
    while x > 0:
        d = w[x][1]
        ans.append(d) 
        x -= d
    ans = ans[::-1]
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  count = 0
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    if s1 < count:
      continue
    count = s1+1
    subindex = index
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (count, i))
      ans[i] = s2
      subindex = i
    index = subindex
    
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  count = 0
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    if s1 < count:
      continue
    count = s1+1
    subindex = index
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (count, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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

for ch in s:
    if ch == '0':
        si.append(0)
    else:
        si.append(1)

ptr = n
ret = []

while ptr > 0:
    for me in range(m, -1, -1):
        if me == 0:
            print(-1)
            exit()
        if ptr - me < 0:
            continue
        if si[ptr-me] == 0:
            ret.append(me)
            ptr -= me
            break

ret.reverse()

print(' '.join(map(str, ret)))

Submission status: Accepted

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

lst = []
i = N
while i > 0:
    for j in range(min(i, M), 0, -1):
        if S[i - j] == '0':
            lst.append(j)
            i -= j
            break
    else:
        print(-1)
        exit()
print(' '.join(map(str, reversed(lst))))

Submission status: Accepted

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

pos = N
res = []
while pos > 0:
  flg = False
  for move in range(M, 0, -1):
    if pos-move < 0:
      continue
    elif S[pos-move] == "0":
      pos -= move
      res.append(move)
      flg = True
      break
    elif S[pos-move] == "1":
      continue
  else:
    print(-1)
    exit()

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

Submission status: Accepted

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

dp = [float('inf')] * (n + 1)
dp[0] = 0

N = n + 1
N0 = 2 ** (N - 1).bit_length()
data = [float('inf')] * (2 * N0)

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

# [a_l, a_(l+1), ..., a_(r-1)]の最小値を求める
def query(l, r):
    L = l + N0
    R = r + N0
    s = float('inf')
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R - 1])

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

update(0, 0)
for i in range(1, n + 1):
    if s[i] == '1':
        continue

    dp[i] = query(max(0, i - m), i) + 1
    update(i, dp[i])

if dp[-1] == float('inf'):
    print(-1)
else:
    cur = n
    target = dp[n] - 1
    arr = [n]

    while cur > 0:
        for i in range(max(0, cur - m), cur):
            if dp[i] == target:
                cur = i
                target -= 1
                arr.append(i)
                break

    arr = arr[::-1]
    ans = []
    for i in range(len(arr) - 1):
        ans.append(arr[i+1] - arr[i])

    for _ans in ans:
        print(_ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = input()[::-1]
idx = 0
ans = [0]
while True:
    flg = False
    step = 0
    for i in range(1, m+1):
        if idx+i <= n:
            if s[idx+i]=='0':
                step = i
                flg = True
    if flg==False:
        break
    else:
        idx += step
    ans.append(idx)

if ans[-1]!=n:
    print(-1)
else:
    ret = []
    for i in range(1,len(ans)):
        ret.append(ans[i]-ans[i-1])
    print(*ret[::-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
S = list(input())
"""
9 3
0001000100
0010001000
3  2   3 1  
"""
S_r = S[::-1] + ["0"] #スタートのぶん付け足し
ans = []
now = 0
while now < n:
    flg = True
    for i in range(m,0,-1):
        if now + i <= n and S_r[now+i] == "0":
            ans.append(i)
            now += i
            flg = False
            break
    if flg:
        print(-1)
        exit()

print(*ans[::-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = input()
s = s[::-1]
ans = []
cur = 0
c = 0
#while cur < n and c < 100:
while cur < n:
    d = n - cur
    r = min(m,d)
    cnt = 0
    for i in range(r):
        x = r - i
        if s[cur + x] == '0':
            ans.append(x)
            cur += x
            #print(x)
            break
        else:
            cnt += 1
    if cnt == r:
        print(-1)
        exit()
    #c += 1
    #print(cur,r)


print(*ans[::-1])