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: Wrong Answer

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 range(m, 1, -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:
    print(*solve(s))

Submission status: Wrong Answer

Solution code:
def solve():
    import sys

    input = sys.stdin.readline

    # seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)
    class SegmentTreeClass:
        # original: @solzard_
        # https://twitter.com/solzard_/status/1180263831596982273
        def __init__(self,
                     init_val: 'initial value: iterable',
                     segfunc: 'operation unique in case',
                     ide_ele: 'identity element corresponding init_val' = 0,
                     ):
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.size = 1 << (len(init_val) - 1).bit_length()
            self.tree = self._build(init_val)

        def _build(self, init_val) -> 'tree':
            segfunc = self.segfunc

            tree = [self.ide_ele] * (self.size * 2 - 1)

            for idx, val in enumerate(init_val, self.size - 1):  # set
                # modify val if needed (e.g. str -> ord())
                tree[idx] = val

            for idx in range(self.size - 2, -1, -1):  # build
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

            return tree

        def update(self, idx: int, val) -> None:
            tree = self.tree
            segfunc = self.segfunc

            idx += self.size - 1
            # modify val if needed as same as in _build()
            tree[idx] = val
            while idx > 0:
                idx = (idx - 1) // 2
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        def query(self, left: int, right: int) -> 'result':
            left += self.size
            right += self.size
            ret = self.ide_ele  # left >= right: return self.ide_ele
            segfunc = self.segfunc
            tree = self.tree
            while left < right:  # どの段も奇偶...順
                if left & 1:  # odd
                    ret = segfunc(ret, tree[left - 1])
                    left += 1
                if right & 1:  # odd
                    right -= 1
                    ret = segfunc(ret, tree[right - 1])
                left >>= 1
                right >>= 1
            return ret

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

    inf = 10 ** 6
    dp = [inf] * (n + 1)
    dp[0] = 0
    # dp[x]:=xへの最小到達回数

    seg = SegmentTreeClass(init_val=dp, segfunc=min, ide_ele=inf)

    for j, s_ in enumerate(s[1:], 1):
        if s_:
            continue
        seg.update(j, seg.query(max(0, j - m), j) + 1)  # maxつけた

    if seg.tree[seg.size - 1 + n] >= inf:
        print(-1)
        return

    order = []
    cf = seg.tree[seg.size - 1 + n] - 1
    cand = inf
    p = seg.size - 1 + n
    for idx in range(seg.size - 1 + n - 1, seg.size - 1 - 1, -1):
        if seg.tree[idx] == cf:
            cand = min(cand, idx)
            if p - cand == m:
                order.append(p - cand)
                p = cand
                cf -= 1
        elif seg.tree[idx] < cf:
            order.append(p - cand)
            p = cand
            cf -= 1

    if p - (seg.size - 1) > 0:
        order.append(p - (seg.size - 1))

    order.reverse()

    print(*order)
    return


solve()

Submission status: Wrong Answer

Solution code:
def solve():
    import sys

    input = sys.stdin.readline

    # seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)
    class SegmentTreeClass:
        # original: @solzard_
        # https://twitter.com/solzard_/status/1180263831596982273
        def __init__(self,
                     init_val: 'initial value: iterable',
                     segfunc: 'operation unique in case',
                     ide_ele: 'identity element corresponding init_val' = 0,
                     ):
            self.segfunc = segfunc
            self.ide_ele = ide_ele
            self.size = 1 << (len(init_val) - 1).bit_length()
            self.tree = self._build(init_val)

        def _build(self, init_val) -> 'tree':
            segfunc = self.segfunc

            tree = [self.ide_ele] * (self.size * 2 - 1)

            for idx, val in enumerate(init_val, self.size - 1):  # set
                # modify val if needed (e.g. str -> ord())
                tree[idx] = val

            for idx in range(self.size - 2, -1, -1):  # build
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

            return tree

        def update(self, idx: int, val) -> None:
            tree = self.tree
            segfunc = self.segfunc

            idx += self.size - 1
            # modify val if needed as same as in _build()
            tree[idx] = val
            while idx > 0:
                idx = (idx - 1) // 2
                tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        def query(self, left: int, right: int) -> 'result':
            left += self.size
            right += self.size
            ret = self.ide_ele  # left >= right: return self.ide_ele
            segfunc = self.segfunc
            tree = self.tree
            while left < right:  # どの段も奇偶...順
                if left & 1:  # odd
                    ret = segfunc(ret, tree[left - 1])
                    left += 1
                if right & 1:  # odd
                    right -= 1
                    ret = segfunc(ret, tree[right - 1])
                left >>= 1
                right >>= 1
            return ret

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

    inf = 10 ** 5 + 10
    dp = [inf] * (n + 1)
    dp[0] = 0
    # dp[x]:=xへの最小到達回数

    seg = SegmentTreeClass(init_val=dp, segfunc=min, ide_ele=inf)

    for j, s_ in enumerate(s[1:], 1):
        if s_:
            continue
        seg.update(j, seg.query(max(0, j - m), j) + 1)  # maxつけた

    if seg.tree[seg.size - 1 + n] >= inf:
        print(-1)
        return

    order = []
    cf = seg.tree[seg.size - 1 + n] - 1
    cand = inf
    p = seg.size - 1 + n
    for idx in range(seg.size - 1 + n - 1, seg.size - 1 - 1, -1):
        if seg.tree[idx] == cf:
            cand = min(cand, idx)
        elif seg.tree[idx] < cf:
            order.append(p - cand)
            p = cand
            cf -= 1
    order.append(p - idx)

    order.reverse()

    print(*order)
    return


solve()

Submission status: Wrong Answer

Solution code:
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 = [[] 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] = dp2[idx] + [i-idx]
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    print(" ".join(map(str, dp2[-1])))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s='0'+input()
if s[-1]=='1':
    print(-1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
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 = 0
ans = []

while True:
    right = bisect_right(A, now + M) - 1
    new = A[right]
    ans.append(new - now)
    if new == N:
        break
    if new == now:
        print(-1)
        exit()
    now = new
print(*ans)

Submission status: Wrong Answer

Solution code:
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])

Submission status: Wrong Answer

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

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

rireki = []

now = 0
while True: 
    for i in range(1,m+1)[::-1]:
        if now + i == n:
            rireki.append(i)
            for i in rireki:
                print(i)
            import sys
            sys.exit()
        elif now + i < n:
            if s[now+i] == "0":
                now += i
                rireki.append(i)
                break
    else:
        print(-1)
        import sys
        sys.exit()

Submission status: Wrong Answer

Solution code:
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=-1
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)

Submission status: Wrong Answer

Solution code:

from sys import exit


ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



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

    op = [0 for i in range(n+1)]

    cnt = 0
    flag = False
    place = []
    for i in range(len(s)):
        if flag and s[i] == '1':
            cnt+=1
            if cnt == m:
                print(-1)
                exit()
        elif s[i] == '1':
            flag = True
            cnt+=1
        else:
            flag = False
            cnt = 0


    r = 0
    for l in range(n+1):
        if s[l] == '0':
            for i in range(r-l+1,m+1):
                if l+i > n:
                    break
                op[l+i] = i
            r = l+m
        if r>=n+1:
            break
        
    print(op)




    ans = []
    op = op[::-1]
    np = 0
    flag = True
    while np < n:
        ans.append(op[np])
        np+=op[np]


    print(*ans[::-1])

    


        


main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

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

li = []

memo = 1
for i in range(1,n+1):
    if s[i-1] != s[i]:
        li.append(memo)
        memo = 1
    else:
        memo += 1
li.append(memo)

for i in range(len(li)):
    li[i] = li[i]-1
    if i%2 == 1:
        if li[i] > m:
            print(-1)
            sys.exit()

ans = []

for i in range(len(li)):
    if i%2 == 1:
        ans.append(li[i])
    else:
        if li[i] > m:
            q = []
            while(li[i] > m):
                li[i]=li[i]-m
                q.append(m)
            q.append(li[i])

            for i in range(len(q)):
                ans.append(q[-i])
        else:
            ans.append(li[i])

print(*ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m = map(int,input().split())
s = str(input())
ans = []
cnt = 0
now = 0
while now != n:
    if n-now <= m:
        ans.append(n-now)
        cnt += 1
        now = n
        break
    for go in range(m,-1,-1):
        if go == 0:
            print(-1)
            exit()
        if s[now+go] == "0":
            ans.append(go)
            now += go
            cnt += 1
            break
ans.sort()
anss = []
now = 0
while now != n:
    for num in ans:
        if s[now+num] != "1":
            anss.append(str(num))
            ans.remove(num)
            now += num
            break
print(" ".join(anss))

Submission status: Wrong Answer

Solution code:
def solve(mid):
    return c[ng-1]-c[mid-1]!=ng-mid
n,m=map(int,input().split())
*s,=map(int,input())
c=s[:]+[0]
for i in range(n):c[i+1]+=c[i]
a=[]
i=0
while i<=n:
    if n-i<=m:
        a+=n-i,
        break
    ok=i # 解が存在する値
    ng=i+m+1 # 解が存在しない値
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid):
            ok=mid
        else:
            ng=mid
    a+=ok-i,
    if i==ok:
        print(-1)
        exit()
    i=ok
    #print(i)
print(*a)

Submission status: Wrong Answer

Solution code:


N,M = map(int, input().split())
S = input()
inv_S =''
for i in range(N):
    inv_S += S[-1-N]

ans = []
flag=0
while len(inv_S) != 0:
    max_len = min(M,len(inv_S))
    for i in range(max_len,0,-1):
        if inv_S[i-1] == '0':
            ans = [i] + ans
            inv_S = inv_S[i:]
            break
        elif i==1:
            flag = -1
            break
    if flag == -1:
        break
    if inv_S =='':
        break
if flag == -1:
    print(-1)
else:
    print(*ans)

Submission status: Wrong Answer

Solution code:
import sys

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

li = []

memo = 1
for i in range(1,n+1):
    if s[i-1] != s[i]:
        li.append(memo)
        memo = 1
    else:
        memo += 1
li.append(memo)

for i in range(len(li)):
    if i%2 == 1:
        if li[i] >= m:
            print(-1)
            sys.exit()

ans = []

for i in range(len(li)):
    if i%2 == 1:
        ans.append(li[i])
    else:
        if li[i] > m:
            q = []
            while(li[i] > m):
                li[i]=li[i]-m
                q.append(m)
            q.append(li[i])

            for i in range(len(q)):
                ans.append(q[-i])
        else:
            ans.append(li[i])

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
s=input()
if m>n:
    m=n
tmp=0
for i in range(m):
    if s[i+1]=="0":
        tmp=i+1
# print(tmp)
li=[]
for i in range(n+1):
    li.append(tmp)
    a=i+1+m
    if a>n:
        a=n
    if s[a]=="0":
        tmp=a
# print(li)
i=0
while(li[i]!=i):
    print(li[i]-i)
    i=li[i]
    if i==n:
        quit()
print(-1)

Submission status: Wrong Answer

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


ans = []

now = N
clear = False
while True:
    
    
    
    for i in range(M):
        if now - M <= 0:
            ans.append(now)
            now = 0
            clear = True
            break
        elif S[now - M + i] == 0:
            ans.append(M-i)
            now = now - M + i
            break
    else:
        break

if clear == True:
    print(len(ans))
    for i in range(len(ans)):
        print(ans[len(ans)-i])
else:
    print("-1")

Submission status: Wrong Answer

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 graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append((b,i))
        g[b].append((a,i))
    return n,g
    
def main():
    n,m=inpm()
    s=input()
    a=str(10**n)
    dp = ['0' for _ in range(n+1)]
    dp[0]='0'
    for i in range(n+1):
        if s[i]=='1':
            dp[n-i]=-1
    for i in range(1,n+1):
        for j in range(max(0,i-m),i):
            if dp[i]==-1 or dp[j]==-1:
                continue
            x=i-j
            y=int(dp[j]+str(x))
            y=str(y)
            if dp[i]=='0':
                dp[i]=y
            elif len(dp[i])==len(y):
                dp[i]=str(max(int(dp[i]),int(y)))
            elif len(dp[i])>len(y):
                dp[i]=y
            elif len(dp[i])<len(y):
                continue
    if int(dp[n])==0:
        print(-1)
    else:
        ans = list(dp[n])
        ans.reverse()
        print(' '.join(ans))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 入力が10**5とかになったときに100ms程度早い
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:
        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])

Submission status: Wrong Answer

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

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

global min_rireki,ans
min_rireki = float("inf")
ans = []
global get_point
get_point = [float("inf") for i in range(n+1)]
get_point[0] = 0

def dfs(pos, rireki):
    global ans
    if pos == n:
        if len(rireki) < min_rireki:
            ans = rireki
    else:
        for i in range(1,m+1)[::-1]:
            if pos + i <= n:
                if s[pos+i] == "0":
                    if get_point[pos+i] - 1 > len(rireki):
                        dfs(pos+i, rireki+[i])
                        get_point[pos+i] = len(rireki) + 1
                        break

dfs(0,[])
if ans == []:
    print(-1)
else:
    for i in ans:
        print(i)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append((b,i))
        g[b].append((a,i))
    return n,g
    
def main():
    n,m=inpm()
    s=input()
    a=str(10**n)
    dp = ['0' for _ in range(n+1)]
    dp[0]='0'
    for i in range(n+1):
        if s[i]=='1':
            dp[n-i]=-1
    for i in range(1,n+1):
        for j in range(max(0,i-m),i):
            if dp[i]==-1 or dp[j]==-1:
                continue
            x=i-j
            y=int(dp[j]+str(x))
            y=str(y)
            if dp[i]=='0':
                dp[i]=y
            elif len(dp[i])==len(y):
                dp[i]=str(max(int(dp[i]),int(y)))
            elif len(dp[i])>len(y):
                dp[i]=y
            elif len(dp[i])<len(y):
                continue
    if int(dp[n])==0:
        print(-1)
    else:
        ans = list(dp[n])
        ans.reverse()
        print(' '.join(ans))
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=list(str(input()))
f=0
mf=0
for i in range(n):
    if s[i]=='1':
        f+=1
        mf=max(mf,f)
    else:
        f=0
if mf>=m:
    print(-1)
    exit()
reans=[]
s.reverse()
nk=-1
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)

Submission status: Wrong Answer

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

max_len = 1
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)

Submission status: Wrong Answer

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

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

global min_rireki,ans
min_rireki = float("inf")
ans = []
global get_point
get_point = [float("inf") for i in range(n+1)]
get_point[0] = 0

def dfs(pos, rireki):
    global ans
    if pos == n:
        if len(rireki) < min_rireki:
            ans = rireki
    else:
        for i in range(1,m+1)[::-1]:
            if pos + i <= n:
                if s[pos+i] == "0":
                    if get_point[pos+i] - 1 > len(rireki):
                        dfs(pos+i, rireki+[i])
                        get_point[pos+i] = len(rireki) + 1

dfs(0,[])
if ans == []:
    print(-1)
else:
    for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
def solve(mid):
    return c[ng-1]-c[mid-1]!=ng-mid
n,m=map(int,input().split())
*s,=map(int,input())
c=s[:]+[0]
for i in range(n):c[i+1]+=c[i]
a=[]
i=0
while i<=n:
    if n-i<=m:
        a+=n-i,
        break
    ok=i # 解が存在する値
    ng=i+m+1 # 解が存在しない値
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve(mid):
            ok=mid
        else:
            ng=mid
    a+=ok-i,
    if i==ok:
        print(-1)
        exit()
    i=ok
    #print(i)
print(*a)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = list(input())
S = [int(s) for s in S]
S.reverse()
dp = [-1 for i in range(N+1)]
dp[0] = 0
for i in range(1, M+1):
	if i > N:
		break
	if S[i] == 0:
		dp[i] = 1

undetermined = M+1
for i in range(1, N):
	if S[i] == 1:
		undetermined = max(undetermined, i+1)
		continue
	for j in range(undetermined, i+M+1):
		if j <= N:
			if S[j] == 0:
				dp[j] = dp[i] + 1
			undetermined = j+1
if dp[N] == -1:
	print(-1)
	exit()

ans = []
prev = (dp[N], N)
for i in range(N-1, -1, -1):
	if dp[i] == -1 or prev[0] == dp[i]:
		continue
	else:
		ans.append(str(prev[1] - i))
		prev = (dp[i], i)

print(" ".join(ans))

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

Solution code:
import heapq
n, m = [int(i) for i in input().split()]

def copy(a):
    return [i.copy() if type(i) is list else i for i in a]
s = input()
path = [[0, (), 0]]
for i in range(1, n + 1):
    if s[i] == "0":
        while True:
            if not path:
                print(-1)
                exit()
            a = heapq.heappop(path)
            if a[2] + m >= i:
                break
        if a[2] + m != i:
            heapq.heappush(path, a)
        a[0] += 1
        a[1] += (i-a[2],)
        a[2] = i
        heapq.heappush(path, copy(a))
print(" ".join([str(i) for i in a[1]]))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
s = input()[::-1]
t  =[]
cnt = 0
st = 0
go = 0
for i in range(len(s)):
    if cnt==M:
        if s[i] == '0':
            t.append(cnt)
            cnt = 0
            go = -1
        else:
            if go==-1 and s[i-1]=='0':
                go = i-1

            if t==[] or  go==-1:
                break
            else:
                t.append(go-t[-1])
                cnt = i-go
                go = -1

    elif s[i] == '1' and s[i-1]=='0':
        go = i-1
    elif i == len(s)-1:
        t.append(cnt)
    cnt += 1

if M==1 and '1' in s:
    print(-1)
elif t ==[]:
    print(-1)
else:
    print(*t[::-1])

Submission status: Wrong Answer

Solution code:
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]


    #dp = [[0 for i in range()] for j in range(n + 1)]
    
    now = 0
    ansl = []
    for i in range(n):
        tm = min(n - now,m)
        while tm > 0 and now+tm<len(s):
            if s[now + tm] == "0":
                now += tm
                ansl.append(tm)
                break
            else:
                tm -= 1
    ansl = ansl[::-1]
    if ansl.count(0) == len(ansl):
        print(-1)
        exit()
    for i in range(len(ansl)):
        if ansl[i] == 0:
            continue
        print(*ansl[i:])
        break

    

    

    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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]


    #dp = [[0 for i in range()] for j in range(n + 1)]
    
    now = 0
    ansl = []
    for i in range(n):
        tm = min(n - now,m)
        while True:
            if s[now + tm] == "0":
                now += tm
                ansl.append(tm)
                break
            else:
                tm -= 1
    ansl = ansl[::-1]
    if ansl.count(0) == len(ansl):
        print(-1)
        exit()
    for i in range(len(ansl)):
        if ansl[i] == 0:
            continue
        print(*ansl[i:])
        break

    

    

    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  s = input()
  if n<= m:
    print(n)
    exit()
  tmp = 0
  for i in range(n+1):
    if s[i] =="1":
      tmp += 1
    else:
      tmp = 0
    if tmp >= m:
      print(-1)
      exit()
  query = deque([(0,"0")])
  while query:
    place,mode = query.popleft()
    if place == n:
      break
    
    for i in range(1,m+1):
      if i+place >= n+1:
        break
      if s[i+place] != "1":
        query.append((i+place,mode+str(i)))
  mode = mode[1::]
  tmp = []
  for i in range(len(mode)):
    tmp.append(mode[i])
    
  print(*tmp)
solve()