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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


INF = -float('inf')
N, M = map(int, input().split())
S = input()[:-1]
Seg = SegmentTree(N+1, lambda a, b: max(a, b), INF)
for i, c in enumerate(reversed(S)):
    if c == "0":
        Seg.set(i, i)
Seg.build()
ans = []
cur = 0

while True:
    nex = Seg.query(min(cur+1, N), min(cur+M+1, N+1))
    if nex == INF:
        ans = [-1]
        break
    else:
        ans.append(nex-cur)
        cur = nex
        if cur == N:
            break
print(" ".join(map(str, reversed(ans))))

Solution (Python):
from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq
dq = deque()
N,M = map(int, input().split())
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [-1 for _ in range(N+1)]
dq.append(0)
for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    idx = dq[0]
    if c != "1" and dp1[idx] != INF:
        dp1[i] = dp1[idx] + 1
        dp2[i] = idx
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    r = []
    s = N
    while True:
        if s == 0:
            break
        ns = dp2[s]
        r.append(s-ns)
        s = ns
    print(" ".join(map(str, r[::-1])))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

n,m=map(int,input().split())
s=input()
if m>n:
    m=n
tmp=-1
for i in range(m):
    if s[-i-2]=="0":
        tmp=-i-2

li=[]
for i in range(n):
    li.append(tmp)
    a=-i-2-m
    if a<-1-n:
        a=-1-n
    if s[a]=="0":
        tmp=a
ans=[]
i=-1
li.reverse()

while(i!=-n-1):

    if li[i]==i:
        print(-1)
        quit()
    ans.append(i-li[i])
    i=li[i]

ans.reverse()


for i in range(len(ans)):
    print(ans[i])

Solution (Python):
import sys

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

def main():
    n,m=MI()
    s=input()[::-1]
    now=0
    ans=[]
    while now<n:
        for d in range(m,0,-1):
            if now+d>n:continue
            if s[now+d]=="0":
                now+=d
                ans.append(d)
                break
        else:
            print(-1)
            exit()
    print(*ans[::-1])

main()

Solution (Python):

n, m = [int(s) for s in input().split()]
s = [int(s) for s in input()]
board = [None]*(n+1)
left = 0
board[left] = 0
for i in range(1,n+1):
    if s[i]:
        continue
    left = max(left, i-m)
    while board[left] is None:
        left += 1
        if left == i:
            break
    if left < i:
        board[i] = left

if board[n] is None:
    print(-1)
else:
    steps = []
    j = n
    while True:
        step = j - board[j]
        steps.append(step)
        j = board[j]
        if j==0:
            break
    print(' '.join(str(s) for s in steps[::-1]))

Solution (Python):
from bisect import bisect_right
N, M = map(int, input().split())
S = input()

A = [i for i, s in enumerate(S) if s == '0']
now = N
ans = []

while True:
    left = bisect_right(A, now - M - 1)
    new = A[left]
    ans.append(now - new)
    if new == 0:
        break
    if new == now:
        print(-1)
        exit()
    now = new

print(*ans[:: -1])

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

if S.find('1'*M) >= 0:
    print(-1)
    exit()

ans = []
i = 0
while i < N:
    a = S[i:i+M+1].rfind('0')
    ans.append(a)
    i += a

print(*ans[::-1])

Solution (Python):
n,m=map(int,input().split())
s=input()
S=[]
for i,ss in enumerate(s):
  if ss=="0":
    S.append(i)
Ans=[]
cur=n
chk=True
import bisect
while cur>0:
  next=S[bisect.bisect_left(S,max(0,cur-m))]
  if next==cur:
    chk=False
    break
  else:
    Ans.append(cur-next)
    cur=next
if not chk:
  print(-1)
else:
  Ans=Ans[::-1]
  print(*Ans)

Solution (Python):
def main():
    N, M  = [int(i) for i in input().split()]
    S  = [int(i) for i in input()]
    loc = N
    a = []
    while loc:
        for i in range(min(loc, M), 0, -1):
            if S[loc - i] == 1:
                continue
            a.append(i)
            loc -= i
            break
        else:
            return '-1'
    return ' '.join(str(i) for i in reversed(a))


print(main())

Solution (Python):
n,m=map(int,input().split())
s=input()
x=n
a=[]
while x!=0:
  for i in range(min(m,x),0,-1):
    if s[x-i]=="0":
      x-=i
      a.append(i)
      break
    if i==1:print(-1);exit()
print(*a[::-1])

Solution (Python):
import sys

def solve():
    N, M = map(int, input().split())
    S = input()
    Ans_rev = []
    current_id = N
    while True:
        length = 0
        for i in range(M):
            if current_id - i - 1 >= 0:
                if S[current_id - i - 1] == "0":
                    length = i + 1
            else: break
        if length > 0: 
            Ans_rev.append(length)
            current_id -= length
        else:
            break
    if current_id > 0: print(-1)
    else:
        Ans = []
        for i in reversed(range(len(Ans_rev))):
            Ans.append(Ans_rev[i])
        print(" ".join(map(str, Ans)))
            

    return 0

if __name__ == "__main__":
    solve()

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


dp=[0]*(n+1)
ans=0
now=n
count=0
flag=True
ans=[]
for i in range(10**11):
    if flag==False:
        break
    for j in range(m,0,-1):
        if now-j<=0:
            ans.append(now)
            flag=False
            break
        elif s[now-j]!='1':
            ans.append(j)
            count+=1
            now-=j
            break
        else:
            if j==1:
                print(-1)
                exit()
            continue
        

ans.reverse()

print(*ans)

Solution (Python):
n, m = map(int, input().split())
a = input()
ret = []
i = n
while i > 0:
    best = max(i - m, 0)
    if a[best] == '1':
        while best < i and a[best] == '1':
            best += 1
        if best == i:
            print(-1)
            exit()
    ret.append(i - best)
    i = best
print(' '.join(map(str, ret[::-1])))

Solution (Python):
class SegTreeIndex(object):
    
    
    __slots__ = ["elem_size", "tree", "default", "op", "index", "op2"]
    def __init__(self, a: list, default=float("inf"), op=lambda a,b: b if a>b else a, op2=lambda a,b:a>b):
        
        
        
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        self.index = index = [0] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        index[elem_size:elem_size + real_size] = list(range(real_size))
        self.default = default
        self.op = op
        self.op2 = op2
        for i in range(elem_size-1, 0, -1):
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]

    def get_value(self, x: int, y: int) -> tuple:  
        l, r = x + self.elem_size, y + self.elem_size
        tree, op, op2, index = self.tree, self.op, self.op2, self.index
        result_l = result_r = self.default
        idx_l = idx_r = -1
        while l < r:
            if l & 1:
                v1, v2 = result_l, tree[l]
                result_l = op(v1, v2)
                if op2(v1, v2)==1:
                    idx_l = index[l]
                l += 1
            if r & 1:
                r -= 1
                v1, v2 = tree[r], result_r
                result_r = op(v1, v2)
                if op2(v1, v2)==0:
                    idx_r = index[r]
            l, r = l >> 1, r >> 1
        result = op(result_l, result_r)
        idx = idx_r if op2(result_l, result_r) else idx_l
        return result, idx

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree, index, op2 = self.op, self.tree, self.index, self.op2
        while i > 1:
            i >>= 1
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]

def main():
    N, M = map(int, input().split())
    S = list(map(int, input()))
    dp = [10 ** 9] * (N + 1)
    seg = SegTreeIndex(dp)
    from_ = [-10000000] * (N + 1)
    seg.set_value(0, 0)
    for i, c in enumerate(S[1:], 1):
        if c == 1:
            continue
        v, idx = seg.get_value(max(i - M, 0), i)
        if v == 1000000000:
            print(-1)
            exit()
        from_[i] = idx
        seg.set_value(i, v + 1)
    n = seg.tree[N + seg.elem_size]
    
    

    Ans = []
    v = N
    while v != 0:
        v_ = from_[v]
        Ans.append(v - v_)
        v = v_
    Ans.reverse()
    print(" ".join(map(str, Ans)))


main()

Solution (Python):
import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

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


p = 0
ans = []
while p < N:
    d = min(M, N - p)
    
    while p + d in out and d >= 1:
        d -= 1
    if d == 0:
        print(-1)
        exit()
    ans.append(d)
    p += d
if p == N:
    ans.reverse()
    print(' '.join(map(str, ans)))
else:
    print(-1)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



from bisect import bisect_right

N,M = II()
A = str(input())

B = A[::-1]

ans = []
place = 0
while place!=N:
    for i in range(1,M+1)[::-1]:
        if place+i<=N:
            if B[place+i]!='1':
                ans.append(i)
                place += i
                break
        if i==1 and B[place+i]=='1':
            print(-1)
            exit()

print(*list(reversed(ans)))

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

i=n
ans=[]
while i>0:
    if i<=m:
        ans.append(i)
        break
    j=m
    while True:
        if j==0:
            print(-1)
            exit()
        if s[i-j]:
            j-=1
        else:
            ans.append(j)
            i-=j
            break


ans.reverse()
print(*ans)

Solution (Python):

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()
S = read()[:-1]
S = S[::-1]
ans = []
cur_i = 0
while True:
    dice = M
    cur_i += dice
    if cur_i > N:
        if N - (cur_i - M) == 0:
            pass
        else:
            ans.append(N - (cur_i - M))
        break
    
    
    
    while S[cur_i] == '1':
        cur_i -= 1
        dice -= 1
        if dice == 0:
            print(-1)
            exit()
    ans.append(dice)
print(*ans[::-1])

Solution (Python):
n, m = map(int, input().split())
s = input()
s = s[::-1]
idx = 0
ans = []
while(True):
    d = s[idx + 1:idx + m + 1].rfind('0')
    if d == -1:
        print(-1)
        break
    ans.append(d + 1)
    idx += d + 1
    if idx == n:
        print(*ans[::-1])
        break

Solution (Python):
n,m=map(int,input().split())
s=list(str(input()))
f=0
mf=0
for i in range(n+1):
    if s[i]=='1':
        f+=1
        mf=max(mf,f)
    else:
        f=0
if mf>=m:
    print(-1)
    exit()
reans=[]
s.reverse()
nk=0
while nk<n:
    for i in range(min(n-nk,m),0,-1):
        if s[nk+i]=='0':
            nk=nk+i
            reans.append(i)
            break
reans.reverse()
print(*reans)

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

Solution (Python):
class SegTreeIndex(object):
    
    
    __slots__ = ["elem_size", "tree", "default", "op", "index", "op2"]
    def __init__(self, a: list, default=float("inf"), op=lambda a,b: b if a>b else a, op2=lambda a,b:a>b):
        
        
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        self.index = index = [0] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        index[elem_size:elem_size + real_size] = list(range(real_size))
        self.default = default
        self.op = op
        self.op2 = op2
        for i in range(elem_size-1, 0, -1):
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]

    def get_value(self, x: int, y: int) -> tuple:  
        l, r = x + self.elem_size, y + self.elem_size
        tree, op, op2, index = self.tree, self.op, self.op2, self.index
        result_l = result_r = self.default
        idx_l = idx_r = -1
        while l < r:
            if l & 1:
                v1, v2 = result_l, tree[l]
                result_l = op(v1, v2)
                if op2(v1, v2)==1:
                    idx_l = index[l]
                l += 1
            if r & 1:
                r -= 1
                v1, v2 = tree[r], result_r
                result_r = op(v1, v2)
                if op2(v1, v2)==0:
                    idx_r = index[r]
            l, r = l >> 1, r >> 1
        result = op(result_l, result_r)
        idx = idx_r if op2(result_l, result_r) else idx_l
        return result, idx

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree, index, op2 = self.op, self.tree, self.index, self.op2
        while i > 1:
            i >>= 1
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]


N, M = map(int, input().split())
S = list(map(int, input()))
dp = [10 ** 9] * (N + 1)
seg = SegTreeIndex(dp)
from_ = [-10000000] * (N + 1)
seg.set_value(0, 0)
for i, c in enumerate(S[1:], 1):
    if c == 1:
        continue
    v, idx = seg.get_value(max(i - M, 0), i)
    if v == 1000000000:
        print(-1)
        exit()
    from_[i] = idx
    seg.set_value(i, v + 1)
n = seg.tree[N + seg.elem_size]



Ans = []
v = N
while v != 0:
    v_ = from_[v]
    Ans.append(v - v_)
    v = v_
Ans.reverse()
print(" ".join(map(str, Ans)))

Solution (Python):
inf = float('inf')


class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        
        self.N = tmp
        
        
        self.Data = [(inf, -1) for _ in range(2*self.N)]

    
    def update(self, k, x):
        
        k += self.N
        
        self.Data[k] = (x, k-self.N)
        
        while k > 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    
    def query(self, l, r):
        
        l += self.N
        r += self.N
        
        res = (inf, -1)
        while l < r:
            
            
            if l & 1:
                res = min([res, self. Data[l]])
                l += 1
            
            
            if r & 1:
                r -= 1
                res = min([res, self.Data[r]])
            l >>= 1; r >>= 1
        return res

    def value(self, k):
        k += self.N
        return self.Data[k]

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

ST = SegmentTree(N+1)
ST.update(0, 0)
memo = [-1] * (N+1)

for i in range(1, N+1):
    l = max(i-M, 0)
    r = i
    if S[i] == "0":
        d, j = ST.query(l, r)
        if d != inf:
            ST.update(i, d+1)
            memo[i] = j

if ST.value(N)[0] == inf:
    print(-1)
    exit()

ans = []
now = N
while now != 0:
    pre = memo[now]
    ans.append(now-pre)
    now = pre

print(*ans[::-1])

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

i=n
ans=[]
while i>0:
    if i<=m:
        ans.append(i)
        break
    j=m
    while True:
        if j==0:
            print(-1)
            exit()
        if s[i-j]:
            j-=1
        else:
            ans.append(j)
            i-=j
            break


ans.reverse()
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline

inf = float('inf')


class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        
        self.N = tmp
        
        
        self.Data = [(inf, -1) for _ in range(2*self.N)]

    
    def update(self, k, x):
        
        k += self.N
        
        self.Data[k] = (x, k-self.N)
        
        while k > 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    
    def query(self, l, r):
        
        l += self.N
        r += self.N
        
        res = (inf, -1)
        while l < r:
            
            
            if l & 1:
                res = min([res, self. Data[l]])
                l += 1
            
            
            if r & 1:
                r -= 1
                res = min([res, self.Data[r]])
            l >>= 1; r >>= 1
        return res

    def value(self, k):
        k += self.N
        return self.Data[k]

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

ST = SegmentTree(N+1)
ST.update(0, 0)
memo = [-1] * (N+1)

for i in range(1, N+1):
    l = max(i-M, 0)
    r = i
    if S[i] == "0":
        d, j = ST.query(l, r)
        if d != inf:
            ST.update(i, d+1)
            memo[i] = j

if ST.value(N)[0] == inf:
    print(-1)
    exit()

ans = []
now = N
while now != 0:
    pre = memo[now]
    ans.append(now-pre)
    now = pre

print(*ans[::-1])

Solution (Python):

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

S.reverse()
ans = []

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

ans.reverse()
print(" ".join(map(str, ans)))

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()


ans = []
S = S[::-1]

pos = [N + 1] * len(S)
p = N + 1
l = N
while p - l <= M and l >= 0:
    pos[l] = p
    l -= 1
p -= 1
while p >= 0:
    if S[p] == '1':
        p -= 1
        continue

    while p - l <= M and l >= 0:
        pos[l] = p
        l -= 1
    p -= 1

i = 0
while i < N:
    me = None
    for j in reversed(range(1, min(M + 1, pos[i] - i + 1))):
        if i + j < len(S) and S[i + j] == '0':
            me = j
            break
    if me is None:
        print(-1)
        exit()
    ans.append(me)
    i += me
print(*ans[::-1])

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

max_len = 0
for i in range(N + 1):
    if S[i] == '0':
        current_len = 0
    else:
        current_len += 1
        max_len = max(current_len, max_len)

if max_len >= M:
    ans = -1
else:
    order = []
    i = N
    while i > 0:
        c = min(M, i)
        while S[i - c] == '1':
            c -= 1
        order.append(str(c))
        i -= c
    ans = ' '.join(order[::-1])

print(ans)

Solution (Python):
import bisect
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def rle(s):
    import itertools
    return list(map(lambda x: (x[0], len(list(x[1]))), itertools.groupby(s)))


n, m = ril()
s = rs()
ls = rle(s)

for a, b in ls:
    if a == '1' and b >= m:
        print(-1)
        exit()

acc = [ls[-1][1]]
for a, b in reversed(ls[:-1]):
    acc.append(acc[-1] + b)

res = []
pos = 0

while True:
    if pos == n:
        break
    i = bisect.bisect(acc, pos + m)
    if i % 2 == 0:
        if pos + m < n + 1:
            res.append(m)
            pos += m
        else:
            res.append(n - pos)
            break
    else:
        new_pos = acc[i - 1] - 1
        res.append(new_pos - pos)
        pos = new_pos
print(*res[::-1])

Solution (Python):

import sys
from collections import Counter
input = sys.stdin.readline
INF = 10**9

n, m = [int(item) for item in input().split()]
s = input().rstrip()
s = s[::-1]
frm = 0
ans = []
ok = True
while frm < n:
    nxt = s[frm:frm+m+1].rfind("0")
    if nxt == 0:
        ok = False
        break
    ans.append(nxt)
    frm += nxt
if not ok:
    print(-1)
else:
    print(" ".join([str(item) for item in ans[::-1]]))

Solution (Python):
n,m = map(int,input().split())
s = input()
a = []
c = n
while True:
  if c <= m:
    a.append(c)
    break
  for i in range(m,0,-1):
    if s[c-i] =='0':
      a.append(i)
      c -= i
      break
    if i == 1:
      print(-1)
      exit()
print(*a[::-1],sep=' ')

Solution (Python):
from bisect import bisect_left

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

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

def solve() :
    ret = []
    cur = N
    while cur != 0 :
        i = bisect_left(reach, cur - M)
        if reach[i] == cur :
            return [-1]
        ret.append(cur - reach[i])
        cur = reach[i]
    
    ret.reverse()
    return ret
    
print(*solve())

Solution (Python):
n,m=map(int,input().split())
s=list(input())
s=list(map(int,s))
dp=[float("inf")]*(n+1)
dp[0]=0

i=n
ans=[]
while i>0:
    if i<=m:
        ans.append(i)
        break
    j=m
    while True:
        if j==0:
            print(-1)
            exit()
        if s[i-j]:
            j-=1
        else:
            ans.append(j)
            i-=j
            break


ans.reverse()
print(*ans)

Solution (Python):
n,m=map(int,input().split())
s=input()
ans=[]
p=n
while p>0:
	flag=False
	k=min(p,m)
	for i in range(min(m,p)):
		if s[p+i-k]=="0":
			flag=True
			ans.append(k-i)
			p=p+i-k
			break
	if flag==False:
		print(-1)
		exit()
print(*ans[::-1])

Solution (Python):
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


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

    now = 0
    ansl = []
    while now != n:
        tm = min(n - now, m)
        pnow = now
        while tm > 0 and now+tm < len(s):
            if s[now + tm] == "0":
                now += tm
                ansl.append(tm)
                break
            else:
                tm -= 1
        
        if pnow == now:
            print(-1)
            exit()
        

    ansl = ansl[::-1]
    for i in range(len(ansl)):
        if ansl[i] == 0:
            continue
        print(*ansl[i:])
        exit()
    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left
n,m = map(int,input().split( ))
s = input()
l= len(s)
s_id = []
sm = 0
for i in range(l):
    if not int(s[i]):
        s_id.append(i)

ans = []
now = n
while now>0:
    
    nxt = now-m
    j = bisect_left(s_id,nxt)
    if s_id[j] <now-m:
        j+=1
    if s_id[j]==now:
        print(-1)
        exit()
    ans.append(now-s_id[j])
    now = s_id[j]
ans.reverse()
print(*ans)

Solution (Python):

from collections import defaultdict
import bisect


def getlist():
	return list(map(int, input().split()))


def main():
	N, M = getlist()
	S = list(input())
	nibu = []
	for i in range(N + 1):
		if S[i] == "0":
			nibu.append(i)

	prev = [None] * (N + 1)
	for i in range(1, N + 1):
		if S[i] == "0":
			s = bisect.bisect_left(nibu, i - M)
			x = nibu[s]
			if x != i:
				prev[i] = x
	
	
	if prev[N] == None:
		print(-1)
	else:
		ans = []
		x = N
		while True:
			ans.append(x - prev[x])
			x = prev[x]
			if prev[x] == None:
				break
		if x == 0:
			ans = ans[::-1]
			print(" ".join(list(map(str, ans))))
		else:
			print(-1)

if __name__ == '__main__':
	main()

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    s = str(readline().rstrip().decode('utf-8'))
    cur = n
    ans = []
    while True:
        b = False
        for i in range(cur - m, cur):
            if 0 <= i < n + 1:
                if s[i] == "0":
                    b = True
                    ans.append(cur - i)
                    cur = i
                    break
        if not b:
            print(-1)
            exit()
        if cur == 0:
            ans.reverse()
            print(*ans)
            exit()


if __name__ == '__main__':
    solve()

Solution (Python):



from collections import Counter,deque


from sys import stdin,setrecursionlimit







setrecursionlimit(10**6)
input=stdin.readline

n,m=map(int,input().split())
s=input().rstrip()
now=n
ans=deque()
while now!=0:
    for i in range(max(0,now-m),now):
        
        if s[i]=="0":
            ans.appendleft(now-i)
            now=i
            break
    else:
        print(-1)
        exit()
print(*ans)

Solution (Python):

from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

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

    ans = []

    t = n
    while True:
        if t <= m:
            ans.append(str(t))
            break
        f = True
        for i in range(m):
            if s[t-m+i] == "0":
                ans.append(str(m-i))
                t = t-m+i
                f = False
                break
        if f:
            print(-1)
            exit()

    ans.reverse()

    print(" ".join(ans))





if __name__ == '__main__':
    main()