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:
class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


N, M = [int(_) for _ in input().split()]
S = [i if v == '0' else 10**5 + 5 for i, v in enumerate(input())]
ST = SegmentTree(S, min, 10**5 + 5)
i = N
ans = [i]
while i:
    i2 = ST.query(max(0, i - M), i)
    if i2 == 10**5 + 5:
        print(-1)
        exit()
    i = i2
    ans += [i]
ans = ans[::-1]
print(' '.join(str(b - a) for a, b in zip(ans, ans[1:])))

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
S = list(map(int,input()))
steps = [N]
i = N
while i > M:
    prev = i
    i -= M
    while S[i] > 0:
        i += 1
    if i >= prev:
        print(-1)
        exit()
    else:
        steps.append(i)
ans = []
cur = 0
while steps:
    prev = cur
    cur = steps.pop()
    ans.append(cur-prev)
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input() # 元の双六
T=S[::-1] # 逆順の双六
l=[]

f=True
i=0 # ゴールから辿る
while i<N:
    t=T[i+1:i+M+1][::-1] # 逆順の双六で今いるマスの1~Mマス先（元の双六ではM~1マス前）
    # print(t) #DB
    if '0' not in t: # 通常のマスがない場合
        f=False
        break
    else: # 通常のマスがある場合
        x=min(M-t.index('0'),len(t)) # 元の双六で，最も手前にある通常のマスまでのマス数
        # print(x) #DB
        l.append(x)
        i+=x
# print(l) #DB

if not f:
    print('-1')
else:
    print(*l[::-1],sep=' ')

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
s = list(input())
s.reverse()
list1 = []
def maze(mass,times): #今いるマス、現状の手数
  if mass+m >= n:
    list1.append(str(n-mass))
    return
  for i in range(m,0,-1):
    if s[mass+i] == "0":
      list1.append(str(i))
      maze(mass+i,times+1)
      return
    elif i == 1:
      print("-1")
      exit()
  return

a = maze(0,0)
list1.reverse()
print(" ".join(list1))

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)
list1 = []
s = list(input())
s.reverse()
def maze(mass): #今いるマス、現状の手数
    if mass+m >= n:
        list1.append(n-mass)
        return
    for i in range(m,0,-1):
        if s[mass+i] == "0":
            list1.append(i)
            maze(mass+i)
            return
        elif i == 1:
            print(-1)
            exit()
maze(0)
list1.reverse()
print(" ".join(map(str,list1)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

N, M = MAP()
S = input()

dp = SegTree(N+1, min, INF)
dp.update(N, 0)
for i in range(N-1, -1, -1):
    # ゲームオーバーマスには遷移できない
    if S[i] == '1':
        continue
    mn = dp.query(i+1, min(N+1, i+M+1))
    if mn != INF:
        dp.update(i, mn+1)

# 辿り着けない
if dp.get(0) == INF:
    print(-1)
    exit()

cnt = dp.get(0)
cur = 0
prev = -1
ans = []
for i in range(1, N+1):
    if dp.get(i) == INF:
        continue
    # 手数が変わる場所でなるべく手前に飛ぶ
    if dp.get(i) != cnt:
        prev = cur
        cur = i
        ans.append(cur-prev)
        cnt = dp.get(i)
print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
S = input()[::-1]

# 地点aから行ける最大位置を返す
def check(a):
    for i in range(min(N, a+M), a, -1):
        if S[i] == '0':
            return i
    return a

i = 0
ans = []
while i < N:
    # 行けるところまで行く
    res = check(i)
    # 1歩も動けなければNG
    if res == i:
        print(-1)
        exit()
    ans.append(res-i)
    i = res
# 逆からやったので、もう1回逆順して出力
print(*ans[::-1])

Submission status: Accepted

Solution code:

def main(n,m,s):

    #i初期化
    i = n
    tmp = []
    while i > 0 :
        for j in range(m,-1,-1):
            if j == 0 :
                i = -1
                break

            if i-j >= 0 :
                if s[i-j] == '0':
                    i -= j
                    tmp.append(j)
                    break
    if i == 0:
        for l in reversed(tmp):
            print(l,end=' ')
    else:
        print(-1)


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

Submission status: Accepted

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

if s.find('1' * m) != -1:
  print('-1')
  exit(0)

i = n
rans = []
flag = True
while flag:
  for j in range(m, 1 - 1, -1):
    if i - j == 0:
      flag = False
    if i - j >= 0 and s[i - j] == '0':
      rans.append(j)
      i = i - j
      break
  
print(' '.join(map(str,reversed(rans))))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
res=[]
now=n
while now!=0:
    j=False
    for i in range(max(0,now-m),now):
        if s[i]=="0":
            j=True
            res.append(now-i)
            now=i
            
            break
    if not j:
        print(-1)
        exit()
for i in range(len(res)-1,-1,-1):
    print(res[i],end=" ")

Submission status: Accepted

Solution code:
import sys
from collections import deque
n,m=map(int,input().split())
s=input()
if n<=m:
    print(n)
    sys.exit()
lst=[0]*(n+1)
for i in range(1,m+1):
    if s[i]=="0":
        lst[i]=i
left=1
right=m+1
k=0
while left<n:
    if s[left]=="0":
        while right-left<=m:
            if s[right]=="0":
                lst[right]=right-left
            right+=1
            if right==n+1:
                k=n
                break
    left+=1
    if left==right or k==n:
        break
if lst[n]==0:
    print(-1)
else:
    ans=deque([])
    while k>0:
        c=lst[k]
        ans.appendleft(c)
        k-=c
    print(*ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=list(input())
l=l[::-1]
now=0
ans=[]
while now<n:
  num=min(n-now,m)#進める最大
  b=True
  for i in range(num):
    num1=num-i
    if l[now+num1]!="1":
      ans.append(str(num1))
      now+=num1
      b=False
      break
  if b:
    now=n+1
if b:
  print(-1)
else:
  ans=ans[::-1]
  print(" ".join(ans))

Submission status: Accepted

Solution code:
N,M = [int(x) for x in input().split()]
S = list(input())
S1 = S[::-1]
ind = 0
ans = []
while ind!=N:
  ind1 = ind
  for i in range(M,0,-1):
    if ind+i<=N and S1[ind+i]=="0":
      ind = ind+i
      ans.append(i)
      break
  if ind1==ind:
    print(-1)
    exit()
print(*ans[::-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
s = S()
now = n
ans = []
while now:
    nxts = s[max(0, now - m): now]
    for i, bit in enumerate(nxts):
        if bit == '0':
            break
    else:
        print(-1)
        exit()
    move = (len(nxts) - i)
    now -= move
    ans += [move]



print(*ans[::-1])

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    s=input()
    masu = n
    res = []
    while masu>m:
        tm = m
        while s[masu - tm]=="1":
            tm -= 1
            if tm == 0:
                return -1
        res.append(tm)
        masu -= tm
    res.append(masu)
    res.reverse()
    return " ".join(map(str,res))


print(main())

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=list(input())
S=S[::-1]
ans=[]
P=0
for i in range(1,N+1):
    if P==N:
        break
    for j in range(M+1):
        if P+(M-j)<=N and S[P+(M-j)]=="0":
            ans.append(M-j)
            P+=M-j
            if M-j==0:
                print(-1)
                exit()
            break
ans=ans[::-1]
if 0 in ans:
    print(-1)
else:
    print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
s = input()
ans = []
cur = n
while cur:
    for d in range(1, min(cur + 1, m + 1))[::-1]:
        if s[cur - d] == '0':
            ans.append(d)
            cur -= d
            break
    else:
        print(-1)
        exit()
print(*ans[::-1], sep=' ')

Submission status: Accepted

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import copy
n, m = map(int, input().split())
s = list(input())
s.reverse()
ans = []
cur_index = 0
while cur_index < n:
    pre = copy.deepcopy(cur_index)
    for i in range(min(m, n - cur_index), 0, -1):
        if s[cur_index + i] == '0':
            cur_index += i
            ans.append(i)
            break
    if pre == cur_index:
        print(-1)
        exit()
ans.reverse()
for i in ans:
    print("{} ".format(i), end = "")

Submission status: Accepted

Solution code:
def main():
	n, m = map(int, input().split())
	rev = input()[::-1]
	ans = []
	cur = nxt = 0
	while cur < n:
		for i in range(cur + 1, cur + m + 1):
			if i==n:
				nxt = i
				break
			if rev[i]=="0":
				nxt = i
		if cur==nxt:
			print(-1)
			exit()
		ans += [str(nxt - cur)]
		cur = nxt
	print(" ".join(ans[::-1]))


if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
su=input()
rev=su[::-1]
if "1"*m in su:
	print(-1)
	exit()
dist_f_n=[float('inf')]*(n+1)
dist_f_n[0]=0
for i in range(1,m+1):
	if rev[i]=="0":
		dist_f_n[i]=1
		last=i
		if i==n:
			break
while last<n:
	for i in range(last+1,last+m+1):
		if rev[i]=="0":
			dist_f_n[i]=dist_f_n[last]+1
			_last=i
			if i==n:
				break
	last=_last
cur=dist_f_n[-1]
_i=0
ans=[]
for i,x in enumerate(dist_f_n[::-1]):
	if x==cur-1:
		ans.append(i-_i)
		cur-=1
		_i=i
print(" ".join(map(str,ans)))

Submission status: Accepted

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

ans = []
x = len(S) - 1
while x:
    for step in range(m, 0, -1):
        if x - step < 0:
            continue
            
        to = S[x-step]
        if to == '1':
            continue
        else:
            x -= step
            ans.append(str(step))
            break
    else:
        print(-1)
        exit()

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

Submission status: Accepted

Solution code:
# from collections import Counter,defaultdict,deque
import sys
# import bisect
# import math
# import itertools
# import string
# import queue
# import copy
# import numpy as np
# import scipy
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
# mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
    
def main():
    n,m=inpm()
    s=list(input())
    s.reverse()
    s=tuple(s)
    ans = []
    now = 0
    while True:
        key = 0
        for go in range(m,0,-1):
            if now+go>=n:
                x=n-now
                ans.append(str(x))
                ans.reverse()
                print(' '.join(ans))
                return
            elif s[now + go]=='0':
                key = 1
                now+=go
                ans.append(str(go))
                break
        if key == 0:
            print(-1)
            return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

DP, prev_i = [0] + [-1] * N, 0
for i in range(N):
    s = S[-2 - i]
    prev_i = max(prev_i, i + 1 - M)
    if s == '0':
        while DP[prev_i] == -1 and prev_i < i + 1:
            prev_i += 1
        if prev_i >= i + 1:
            break
        DP[i + 1] = DP[prev_i] + 1

if DP[-1] == -1:
    print(-1)
else:
    df, ans = [0] * (DP[-1] + 1), []
    for i in range(N + 1):
        if DP[i] >= 1:
            df[DP[i]] = i
    for i in range(DP[-1]):
        ans.append(df[-1 - i] - df[-2 - i])
    print(' '.join(map(str, ans)))

Submission status: Accepted

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

ans = []
C = -1
lastZero = 0
lastStop = 0
flag = True
for i, v in enumerate(S):
    C += 1
    if v == '0':
        lastZero = i
    elif i - lastZero >= M:
        flag = False
        break
    if C == M:
        ans.append(lastZero - lastStop)
        lastStop = lastZero
        C = i - lastStop
    elif i == N:
        ans.append(C)

if flag:
    for i in range(len(ans)-1, -1, -1):
        print(ans[i],end='')
        if i > 0:
            print(' ',end='')
        else:
            print()
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
s = input()
ans = []
p = n
while m < p:
    for i in range(m, 0, -1):
        if s[p - i] == "0":
            ans.append(i)
            break
        else:
            if i == 1:
                print(-1)
                exit()
            else:
                continue
    p -= i
ans.append(p)
k = len(ans)
for i in range(k):
    if i == k-1:
        print(ans[k-i-1])
    else:
        print(ans[k-i-1], end=" ")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
cur=N
can_points=[N]
while cur>0:
  point=cur
  for i in range(min(M,cur)):
    if int(S[cur-1-i])==0:
      point=cur-1-i
  if point==cur:
    break
  else:
    cur=point
    can_points.append(point)
if cur>0:
    print(-1)
else:
    l=[]
    s=len(can_points)
    for i in range(s-1):
        l.append(str(can_points[s-2-i]-can_points[s-1-i]))
        l.append(' ')
    print(''.join(l))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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


def solve(x):
    if x <= m + 1:
        return [x - 1]
    for i in range(m, 0, -1):
        if s[x - 1 - i] == 0:
            cand = solve(x - i)
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(len(s)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = input()
S = S[::-1]
s = 0
used = [0]
while s < N:
    for i in range(M,-1,-1):
        if s+i > N:
            i = N-s
        if S[s+i]=='0':
            s += i
            used.append(s)
            break
    if i==0:
        break
if s==N:
    ans = []
    for i in range(len(used)-1):
        ans.append(used[i+1]-used[i])
    ans = ans[::-1]
    ans = ' '.join([str(c) for c in ans])
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    if m == 1:
        ans = [1] * n
    else:
        ans = solve(s)
    print(*ans)

Submission status: Accepted

Solution code:

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

S_inv = S[::-1]
count = 0
ans_inv = []
flag = True
flag2 = True

while flag:
    for i in range(M):
        if len(S_inv) - count - 1 < M:
            if len(S_inv) - count - 1 != 0:
                ans_inv.append(len(S_inv) - count - 1)
            flag = False
            break
        elif S_inv[count + M - i] == "0":
            count += M - i
            ans_inv.append(M - i)
            break
    else:
        flag2 = False
        break

if flag2:
    print(*ans_inv[::-1])
else:
    print(-1)

Submission status: Accepted

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


# If at i can go to j,k and from j can go to l then can also go to l from k since (j-l) < m => (k-l) < m
# so it is always best to take the highest move possible from i
# Reversing to get max moves

def getFarthest(start):
    for i in range(min(n,start+m),start-1,-1):
        if s[i] == '0':
            return i

ans = []
start = 0
found = True
while True:
    nxt = getFarthest(start)
    if nxt == start:
        found = False
        break
    ans.append(nxt - start)
    start = nxt
    if start == n:
        break
ans = ans[::-1]
if found:
    for i in ans:
        print(i,end=" ")
    print()
else:
    print(-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:
import collections
import heapq
def main():

    N, M = map(int, input().split())
    S = input()
    h = []
    w = []
    heapq.heappush(h, [0, N])
    heapq.heappush(w, [0, N])
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            while h:
                n, p = heapq.heappop(h)
                if p-i <= M:
                    heapq.heappush(h, [n+1, i])
                    heapq.heappush(w, [n+1, i])
                    heapq.heappush(h, [n, p])
                    break
            if len(h) == 0: return -1
        # print(h)

    ans = []
    n, p = heapq.heappop(w)
    # print(h)
    while w:
        m, q = heapq.heappop(w)
        if m == n + 1:
            ans.append(p-q)
            n = m
            p = q
    return " ".join(map(str, ans[::-1]))

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
S = list(map(int,input()))
steps = [N]
i = N
while i > M:
    prev = i
    i -= M
    while S[i] > 0:
        i += 1
    if i >= prev:
        print(-1)
        exit()
    else:
        steps.append(i)
ans = []
cur = 0
while steps:
    prev = cur
    cur = steps.pop()
    ans.append(cur-prev)
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()[::-1]
step=[]
proceed=0
while proceed<n:
  if s[proceed+1:min(proceed+m+1,n)]=="1"*m:
    print(-1);exit()
  else:
    check=proceed+m
    if s[min(check,n)]=="0":
      step.append(min(check,n)-proceed)
      proceed=min(check,n)
      #print(proceed)
    else:
      while s[min(check,n)]=="1":
        if s[min(check,n)-1]=="0":
          step.append(min(check,n)-1-proceed)
          proceed=min(check,n)-1
          break
        #print(proceed,check)
        check-=1
print(*step[::-1])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = input()
N0 = 2**(N-1).bit_length()
INF = 2**31-1

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

# [l,r)の最小値
def query(l, r, data):
    L = l + N0; R = r + N0
    s = 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



data1 = [INF]*(3*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(max(0,n-M+1),n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(3*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(max(0,n-M+1),n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)

Submission status: Accepted

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

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


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


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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


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


#main
if __name__ == '__main__':
    solve()