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:
N, M = map(int, input().split())
S = list(map(int, list(input())))
S.reverse()

ans = []

i=0
while i < N:
  max = 0
  for j in range(1, M+1):
    if i + j < N+1:
      if S[i+j] == 0:
        max = j
  if max == 0:
    print(-1)
    exit()
  ans.insert(0, max)
  i += max
for i in ans:
  print(i,end=" ")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A,c,dp,r=[0]*N,0,0,[]
for i, s in enumerate(reversed(input())):
    if s=="1":c+=1;A[i]=c
    else:c=0
while dp+M<=N-1:
    t = M-A[dp+M]
    if t>0: dp+=t
    else:print(-1);exit()
    r.append(t)
r.append(N-dp)
print(*reversed(r))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
S = input().rstrip()
A = [0]*N
cnt = 0
S = reversed(S)
for i, s in enumerate(S):
    if s=="1":
        cnt += 1
        A[i] = cnt
    else:
        cnt = 0
dp = 0
res = []
while dp+M <= N-1:
    t = M - A[dp+M]
    if t>0:
        dp += t
    else:
        print(-1)
        exit()
    res.append(t)
res.append(N-dp)
res.reverse()
print(*res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input().rstrip()
A = [0]*N
cnt = 0
S = reversed(S)
for i, s in enumerate(S):
    if s=="1":
        cnt += 1
        A[i] = cnt
    else:
        cnt = 0
dp = 0
res = []
while dp+M <= N-1:
    t = M - A[dp+M]
    if t>0:
        dp += t
    else:
        print(-1)
        exit()
    res.append(t)
res.append(N-dp)
res.reverse()
print(*res)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
S = input()[::-1]
ans = ''
i = 0
while i < N - M:
    found = False
    for j in range(M, 0, -1):
        if S[i + j] == '0':
            ans += str(j) + ' '
            i += j
            found = True
            break
    if not found:
        print(-1)
        sys.exit()
ans += str(N-i)
print(' '.join(ans.split()[::-1]))

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, m = getList()
    li = []
    ans = []
    for i, c in enumerate(getS()):
        if c == "0":
            li.append(i)
    cur = n
    while True:
        # print(ans)
        ins = cur - m
        ind = bisect_left(li, ins)
        tgt = li[ind]
        if cur == tgt:
            print(-1)
            return

        ans.append(cur - tgt)
        if tgt == 0:
            break
        cur = tgt

    ans.reverse()
    print(*ans)





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N, M = in_nn()
    S = in_s()

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=[]
s=s[::-1]

now=0
while now<n:
    for i in range(m,0,-1):
        if now+i<=n and s[now+i]=="0":
            ans.append(i)
            now=now+i
            break
    else:
        print(-1)
        break
else:
    ans=[str(i) for i in ans]
    print(" ".join(ans[::-1]))

Submission status: Accepted

Solution code:
from collections import deque

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

if M >= N:
  print(N)
  exit()
  
q = deque([])

i = 0
j = 0
while i < N:
  f = 0
  for k in range(i+M,j,-1):
    if S[k] == '0':
      f = 1
      break
  j = i + M
  q.appendleft(k-i)
  i = k
  if f == 0:
    print(-1)
    exit()

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

Submission status: Accepted

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

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

def cost(S):
    minCost = [-1]*(N+1)
    minCost[0] = 0
    ind = 1
    for i,s in enumerate(S):
        if s == "1":
            continue
        while i < ind <= min(i+M, N):
            if S[ind] == "0":
                minCost[ind] = minCost[i] + 1
            ind += 1
    return minCost

M1 = cost(S)
M2 = cost(S[::-1])[::-1]
if M1[-1] == -1:
    print(-1)
else:
    C = M1[-1]
    Inds = [10**14]*(C+1)
    for i, (m1, m2) in enumerate(zip(M1, M2)):
        if m1 + m2 == C:
            Inds[m1] = min(Inds[m1], i)
    ans = []
    for i1, i2 in zip(Inds, Inds[1:]):
        ans.append(i2-i1)
    print(*ans)

Submission status: Accepted

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

s.reverse()
ng = False
c = 0
ans = []
while ng == False and c < n:
    for i in range(m, 0, -1):
        if c+i < n+1 and s[c+i] == '0':
            c += i
            ans.append(str(i))
            break
        elif i == 1:
            ng = True
if ng:
    print(-1)
else:
    ans.reverse()
    print(' '.join(ans))

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, M, S):
    ans = []
    i = N
    while i > 0:
        for j in range(max(0, i - M), i):
            if S[j] == '0':
                ans.append(i - j)
                i = j
                break
        else:
            print(-1)
            return
    print(*list(reversed(ans)))

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = input().rstrip()
    main(N, M, S)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
 
x = n
roulette = []
while x > m:
    for i in range(m, 0, -1):
        if s[x-i] == '0':
            x -= i
            roulette.append(i)
            break
    else:
        print(-1)
        exit()
roulette.append(x)
roulette.reverse()
print(' '.join(map(str, roulette)))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

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

m = N
record = []
while True:
    for i in range(M,-1,-1):
        if i == 0:
            print(-1)
            sys.exit()
        if m-i < 0: continue
        if S[m-i] == "0":
            m = m - i
            record.append(str(i))
            if m == 0:
                print(" ".join(reversed(record)))
                sys.exit()
            break

Submission status: Accepted

Solution code:
def solve():
  N, M = map(int, input().split())
  S = input()
  ans = []
  visited = [False]*(N+1)
  visited[-1] = True
  now = N
  while True:
    i = min(M,now)
    visited[now-i] = True
    while S[now-i]=='1':
      i -= 1
      if visited[now-i]==True:
        return [-1]
      visited[now-i] = True
    ans.append(i)
    if now-i==0:
      return ans[::-1]
    now -= i
print(*solve())

Submission status: Accepted

Solution code:
# F - Sugoroku
import sys
sys.setrecursionlimit(10 ** 9)

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

# r[i]:sを後ろから見ていって、iから最小何手でゴールするかを求める。
INF = float('inf')
r = [INF for _ in range(n+1)]
r[n] = 0
idx = n
for i in range(n-1,-1,-1):
  while(idx-i > m or r[idx] == INF):
    idx -= 1
  if idx <= i:
    print(-1)
    exit()
  if s[i] == '0':
    r[i] = r[idx]+1
    p = r[i]
#print(r)

# rを先頭から見ていき、rの数字が変わる直前まで進むようにすれば
# 最短で辞書順最小なルートが求まる。
ans = []
c = 0
for i in range(n+1):
  if r[i] != INF and r[i] != p:
    p = r[i]
    ans.append(c)
    c = 1
  else:
    c += 1
print(*ans)

# mnr = [m for _ in range(n+1)]
# mnl = n+1
# def dfs(x,c):
#   global mnr,mnl
#   #print(x,c)
#   if x == n:
#     #print(r)
#     if len(r) < mnl or (len(r) == mnl and r < mnr):
#       mnr = r[:]
#       mnl = len(r)
#     return True
#   if c >= mnl or x > n or s[x] == '1':
#     return False
#   for i in range(m,0,-1):
#     r.append(i)
#     dfs(x+i,c+1)
#     r.pop()
# dfs(0,0)
# if mnl < n+1:
#   print(*mnr)
# else:
#   print(-1)

Submission status: Accepted

Solution code:
# F - Sugoroku
import sys
sys.setrecursionlimit(10 ** 9)

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

# r:sを後ろから見ていって、最小何手でゴールするかを求める。
INF = float('inf')
r = [INF for _ in range(n+1)]
r[n] = 0
idx = n
for i in range(n-1,-1,-1):
  while(idx-i > m or r[idx] == INF):
    idx -= 1
  if idx <= i:
    print(-1)
    exit()
  if s[i] == '0':
    r[i] = r[idx]+1
    p = r[i]
#print(r)

# rを先頭から見ていき、rの数字が変わる直前まで進むようにすれば
# 最短で辞書順最小なルートが求まる。
ans = []
c = 0
for i in range(n+1):
  if r[i] != INF and r[i] != p:
    p = r[i]
    ans.append(c)
    c = 1
  else:
    c += 1
print(*ans)

# mnr = [m for _ in range(n+1)]
# mnl = n+1
# def dfs(x,c):
#   global mnr,mnl
#   #print(x,c)
#   if x == n:
#     #print(r)
#     if len(r) < mnl or (len(r) == mnl and r < mnr):
#       mnr = r[:]
#       mnl = len(r)
#     return True
#   if c >= mnl or x > n or s[x] == '1':
#     return False
#   for i in range(m,0,-1):
#     r.append(i)
#     dfs(x+i,c+1)
#     r.pop()
# dfs(0,0)
# if mnl < n+1:
#   print(*mnr)
# else:
#   print(-1)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

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

ide_ele = float('inf')

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        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 += 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):
        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

# 最短手数k回でクリアできるとすると、
# 1 ~ M　の内１つをk回選んで合計をNにする
N, M = getNM()
S = input()
trap = set()
for i in range(len(S)):
    if S[i] == '1':
        trap.add(i)

# これABC011 123引き算と同じでは

# 案1 dpを使う
# dp[i]: iマスに止まる時の最短手順
# dp[i]の時 dp[i + 1] ~ dp[i + M]についてmin(dp[i] + 1, dp[i + j])を見ていく
# 決まったらdpを前から見ていき最短手順がdp[i] - 1になるものを探す（辞書順）
# → M <= 10 ** 5より多分無理

# セグ木使えばいける？
# dp[i] = dp[i - M] ~ dp[i - 1]の最小値 + 1
# dp[i - M] ~ dp[i - 1]の最小値はlogNで求められるので全体でNlogN

dp = [float('inf')] * (N + 1)
dp[0] = 0
seg = SegTree([float('inf')] * (N + 1), segfunc, ide_ele)
seg.update(0, 0)

# dp[i]をレコード
for i in range(1, N + 1):
    # もしドボンマスなら飛ばす（float('inf')のまま）
    if i in trap:
        continue
    # dp[i - M] ~ dp[i - 1]の最小値をサーチ
    min_t = seg.query(max(0, i - M), i)
    seg.update(i, min_t + 1)
    dp[i] = min_t + 1

# goalに到達できないなら
if dp[-1] == float('inf'):
    print(-1)
    exit()

# 何回の試行で到達できるかをグルーピング
dis = [[] for i in range(dp[-1] + 1)]
for i in range(len(dp)):
    if dp[i] == float('inf'):
        continue
    dis[dp[i]].append(i)

# ゴールから巻き戻っていく
now = dp[-1]
now_index = N
ans = []
# 辞書順で1 4 4 < 3 3 3なので
# 一番前にできるだけ小さい数が来るようにする
for i in range(now, 0, -1):
    # dp[i] - 1回で到達できる
    # 現在地点からMマス以内
    # で最も現在地点から遠いところが１つ前のマス
    index = bisect_left(dis[i - 1], now_index - M)
    # サイコロの目を決める
    ans.append(now_index - dis[i - 1][index])
    # 現在地点更新
    now_index = dis[i - 1][index]

for i in ans[::-1]:
    print(i)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

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

ide_ele = float('inf')

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        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 += 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):
        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

# 最短手数k回でクリアできるとすると、
# 1 ~ M　の内１つをk回選んで合計をNにする
N, M = getNM()
S = input()
trap = set()
for i in range(len(S)):
    if S[i] == '1':
        trap.add(i)

# 案1 dpを使う
# dp[i]: iマスに止まる時の最短手順
# dp[i]の時 dp[i + 1] ~ dp[i + M]についてmin(dp[i], dp[i + j] + 1)を見ていく
# 決まったらdpを前から見ていき最短手順がdp[i] - 1になるものを探す（辞書順）
# → M <= 10 ** 5より多分無理

# セグ木使えばいける？
# dp[i]についてdp[i - M] ~ dp[i - 1]の最小値 + 1

dp = [float('inf')] * (N + 1)
dp[0] = 0
seg = SegTree([float('inf')] * (N + 1), segfunc, ide_ele)
seg.update(0, 0)

for i in range(1, N + 1):
    if i in trap:
        continue
    min_t = seg.query(max(0, i - M), i)
    seg.update(i, min_t + 1)
    dp[i] = min_t + 1

if dp[-1] == float('inf'):
    print(-1)
    exit()

dis = [[] for i in range(dp[-1] + 1)]
for i in range(len(dp)):
    if dp[i] == float('inf'):
        continue
    dis[dp[i]].append(i)

now = dp[-1]
now_index = N
ans = []
for i in range(now, 0, -1):
    index = bisect_left(dis[i - 1], now_index - M)
    ans.append(now_index - dis[i - 1][index])
    now_index = dis[i - 1][index]

for i in ans[::-1]:
    print(i)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = map(int, readline().split())
    s = input()
    t = [0] * (n + 1)

    cur = n
    for i in range(n, -1, -1):
        if s[i] == "0":
            cur = i
            t[i] = cur
        else:
            t[i] = cur

    res = []

    i = n
    while i > 0:
        nx = max(0, i - m)
        if t[nx] == i:
            return print(-1)
        else:
            res.append(i - t[nx])
            i = t[nx]

    print(*res[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

i = N
ans = []
while i > 0:
    for j in reversed(range(1, M + 1)):
        if i - j >= 0 and S[i - j] == "0":
            ans.append(j)
            i -= j
            break
    else:
        ans = []
        break

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

Submission status: Accepted

Solution code:
n, m = (int(x) for x in input().split())
s = input()
t = list(reversed(s))

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

print(*reversed(ANS))

Submission status: Accepted

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

for i in range(1,n+1):
    if s[i]=='1':
        continue
    for j in range(max(0,i-m),i):
        if s[j]=='1':
            continue
        if a[j]>0:
            break
    
    a[i]=i-j

ans=''

cur=n
while cur>0:
    d=a[cur]
    cur-=d
    if d==0:
        print(-1)
        exit(0)

    ans=str(d)+' '+ans

print(ans[:-1])

Submission status: Accepted

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

Submission status: Accepted

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

    ans = []
    cur = N
    ecur = cur - 1
    while cur > 0:
        ncur = cur
        while (cur - ecur) <= M and ecur >= 0:
            if G[ecur] == 0:
                ncur = ecur
            ecur -= 1

        if ncur == cur:
            print(-1)
            return

        ans.append(cur - ncur)
        cur = ncur

    ans.reverse()

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
S=S[::-1]
now = 0
ok=1
history = []
while True:
  for i in range(min(M, N-now),0,-1):
    if S[now+i] == '0':
      now += i
      history.append(str(i))
      break
    if i==1:
      print(-1)
      ok=0
      break
  if ok==0:break
  if now == N:break

if ok==1:print(' '.join(history[::-1]))

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_right
INFTY = 10**6
N,M = map(int,input().split())
S = input().strip()
dp = [INFTY for _ in range(N+1)]
dp[N]=0
A = deque([])
B = {}
pre = N
flag = 0
for i in range(N-1,-1,-1):
    if S[i]=="0":
        ind = bisect_right(A,i+M)
        if ind>0:
            dp[i] = dp[A[ind-1]]+1
            B[i] = A[ind-1]
            if dp[i]>dp[pre]:
                A.appendleft(pre)
        else:
            if pre<=i+M:
                dp[i]=dp[pre]+1
                B[i] = pre
                A.appendleft(pre)
            else:
                flag = 1
                break
        pre = i
if flag==0:
    P = []
    k = 0
    while k<N:
        P.append(B[k]-k)
        k = B[k]
    print(*P)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
S = list(input())

def solve():
    now = N
    choice = []
    while 1:
        if now==0:
            return choice[::-1]
        for m in range(M, 0, -1):
            nx = now-m
            if nx<0: continue
            if S[nx]=='1': continue
            now = nx
            choice.append(m)
            break
        else:
            return [-1]

print(*solve())

Submission status: Accepted

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

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

print(*ans[::-1])

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
s=input()
ans=[]
current=n
while current>0:
  for i in range(m):
    if current-(m-i)<0:
      continue
    if s[current-(m-i)]=='0':
      current-=(m-i)
      ans.append(str(m-i))
      break
    if i==m-1:
      print(-1)
      sys.exit()
ans.reverse()
print(' '.join(ans))

Submission status: Accepted

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

S.reverse()
ans = []
i = 0
while i < N:
    num = 0
    for j in range(min(N, i+M), i, -1):
        if S[j] == "0":
            num = j-i
            i = j
            break
    if num == 0:
        ans = -1
        break
    ans.append(num)

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

Submission status: Accepted

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

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 = list(map(int, input().split()))
s = input()
c = n
ans = []
while c>0:
    val = None
    for i in range(1,m+1):
        if c-i>=0 and s[c-i]=="0":
            val = i
    if val is None:
        ans = -1
        break
    c = c-val
    ans.append(val)
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()
ans = []
cur = N
while cur != 0:
    for step in range(M, 0, -1):
        if cur - step < 0:
            continue
        if s[cur-step] == '1':
            continue
        ans.append(step)
        cur -= step
        break
    else:
        print(-1)
        exit()
print(*ans[::-1])

Submission status: Accepted

Solution code:
import heapq


def main():
    N, M = list(map(int, input().split(' ')))
    S = input()
    # 最短手数のdpテーブルを作る
    T = S[::-1]  # ゴールから逆順にたどる（最後に逆にする）
    dp = [-1] * (N + 1)
    que = [0] * M
    for i, t in enumerate(T):
        if i == 0:
            dp[0] = 0
            continue
        if len(que) == 0:
            print(-1)
            return
        index = heapq.heappop(que)
        if t == '1':
            continue
        dp[i] = 1 + dp[index]
        while len(que) < M:
            heapq.heappush(que, i)
    dp.reverse()
    # 細切れに進んでいく
    path = list()
    target = dp[0] - 1
    cnt = 0
    for i in range(N + 1):
        if dp[i] != target:
            cnt += 1
        else:
            path.append(cnt)
            cnt = 1
            target -= 1
    print(' '.join(map(str, path)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    N, M = Scanner.map_int()
    S = Scanner.string()
    pos = N
    ans = []
    while pos > 0:
        for i in range(max(pos - M, 0), pos):
            if S[i] == '0':
                ans.append(pos - i)
                pos = i
                break
        else:
            print(-1)
            return
    print(*ans[::-1])


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
s = ''.join(reversed(s))
ans = []
index = 0
while index < n:
    next_index = -1
    for j in range(min(index + m, n), index, -1):
        if s[j] == '0':
            next_index = j
            break
    if next_index == -1:
        ans = [-1]
        break
    ans.append(next_index - index)
    index = next_index 
print(' '.join(list(map(str, list(reversed(ans))))))

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
S=list(input())
T=S[::-1]
D=[0]*N
if N<=M:
  print(N)
  exit()
renzoku,ma=0,0
for i in range(1,N+1):
  if S[i]=='1':
    renzoku+=1
  else:
    ma=max(ma,renzoku)
    renzoku=0
if ma>=M:
  print(-1)
  exit()
r=0
for i in range(1,M+1):
  if T[i]!='1':
    r=i
ans=[r]

while r+M<N:
  for i in range(M,0,-1):
    if T[r+i]=='0':
      ans.append(i)
      r+=i
      break
  
ans.append(N-r)
print(*ans[::-1])

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
S=list(input())
T=S[::-1]
D=[0]*N
if N<=M:
  print(N)
  exit()
r=0
renzoku,ma=0,0
for i in range(1,N+1):
  if S[i]=='1':
    renzoku+=1
  else:
    ma=max(ma,renzoku)
    renzoku=0
if ma>=M:
  print(-1)
  exit()

for i in range(1,M+1):
  if T[i]!='1':
    D[i]=1
    r=i
  else:
    D[i]=100000
ans=[r]

while r+M<N:
  for i in range(M,0,-1):
    if T[r+i]=='0':
      ans.append(i)
      r+=i
      break
  
ans.append(N-r)
print(*ans[::-1])

Submission status: Accepted

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

steps = []
c = N
flg = True
while flg:
    if c <= M:
        steps.append(c)
        break
    
    for i in reversed(range(1, M + 1)):
        if S[c - i] == "0":
            steps.append(i)
            c -= i
            break
        if i == 1:
            steps = [-1]
            flg = False
            
print(*steps[::-1])

Submission status: Accepted

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

tmp = 0
sum1 = 0
ans = []

while tmp < n:
    for i in range(m, 0, -1):
        flag = False
        if tmp + i <= n:
            if s[tmp+i] == '0':
                tmp += i
                flag = True
                sum1 += 1
                ans.append(i)
                break
    if not flag:
        print(-1)
        exit()

for i in ans[::-1]:
    print(i, end = ' ')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
s = s[::-1]
loc = 0
anslist=[]
while True:
  if loc >= n-m:
    anslist.append(n-loc)
    break
    quit()
  next = m
  while s[loc+next]=="1":
    next-=1
    if next == 0:
      print(-1)
      quit()
  anslist.append(next)
  loc+=next
ans=anslist[::-1]
ans = list(map(str, ans))
print(" ".join(ans))