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:
n,m = map(int, input().split())
s = input()

cnt=0
for i in range(len(s)):
    if s[i]=="1":
        cnt+=1
        if cnt>=m:
            print(-1)
            exit()
    else:
        cnt=0

cnt=0
from collections import defaultdict
d = defaultdict(int)
d[cnt]=n
for i in reversed(range(len(s))):
    if s[i]=="1":
        continue
    if d[cnt] - i <= m:
        d[cnt+1]=i
    else:
        cnt+=1
d[cnt+1]=0


ans=[]
for i in reversed(range(len(d)-1)):
    ans.append(d[i] - d[i+1])
print(*ans,sep=" ")

Submission status: Wrong Answer

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

cnt=0
for i in range(len(s)):
    if s[i]=="1":
        cnt+=1
        if cnt>=m:
            print(-1)
            exit()

cnt=0
from collections import defaultdict
d = defaultdict(int)
d[cnt]=n
for i in reversed(range(len(s))):
    if s[i]=="1":
        continue
    if d[cnt] - i <= m:
        d[cnt+1]=i
    else:
        cnt+=1
d[cnt+1]=0

ans=[]
for i in reversed(range(len(d)-1)):
    ans.append(d[i] - d[i+1])
print(*ans,sep=" ")

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
S=input()
lst=[]
koma=N
rs=0
ME=0
pn=0
while koma>0 and pn==0:
 rs+=1
 if int(S[koma-rs])==0:
  ME=rs
 if koma-rs==0 or rs==M:
  lst.append(ME)
  if ME==0:
   pn+=1
  koma-=ME
  rs=rs-ME
if pn>0:
 print(-1)
else:
 lst.reverse()
 print(*lst)

Submission status: Wrong Answer

Solution code:

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


class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        # self.array[actual_x] = self.operator(self.array[actual_x],val)
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

    def find(self, l, r):
        #findの方が高速?
        l += self.num_leaves
        r += self.num_leaves+1
        ret = self.identity
        while l < r:
            if l & 1:
                ret = self.operator(ret, self.array[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.operator(ret, self.array[r])
            l //= 2
            r //= 2
        return ret

st = segtree(n+1,min,1e10)

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

st.build(arr)

for i in range(1,n+1):
    if s[i] == "1":
        continue
    else:
        left = max(i-m,0)
        right = i-1
        tm = st.find(left,right)
        arr[i] = tm+1
        st.update(i,tm+1)




nowm = arr[-1]
right = []
left = []

if nowm > 1e9:
    print(-1)
else:
    # print(arr)
    ans = [0]
    st = arr[0]
    for i in range(1,n+1):
        if st < arr[i] and arr[i] < 1e7:
            ans.append(i)
            st = arr[i]
    ans[-1] = n
    for i in range(len(ans)-2):
        print(ans[i+1]-ans[i],end=" ")
    print(ans[-1]-ans[-2])

Submission status: Wrong Answer

Solution code:

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


class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        # self.array[actual_x] = self.operator(self.array[actual_x],val)
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

    def find(self, l, r):
        #findの方が高速?
        l += self.num_leaves
        r += self.num_leaves+1
        ret = self.identity
        while l < r:
            if l & 1:
                ret = self.operator(ret, self.array[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.operator(ret, self.array[r])
            l //= 2
            r //= 2
        return ret

st = segtree(n+1,min,1e10)

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

st.build(arr)

for i in range(1,n+1):
    if s[i] == "1":
        continue
    else:
        left = max(i-m,0)
        right = i-1
        tm = st.find(left,right)
        arr[i] = tm+1
        st.update(i,tm+1)




nowm = arr[-1]
right = []
left = []

if nowm > 1e9:
    print(-1)
else:
    arr.append(1e8)
    nowm = arr[-1]
    for i in range(2,n+3):
        if nowm > arr[-i]:
            nowm = arr[-i]
            right.append(-i)
            left.append(-i)
        elif nowm == arr[-i]:
            left[-1] = -i
    # print(arr)
    # print(right)
    # print(left)
    bef = right[0]
    ans = []
    for i in range(len(left)-1):
        ans.append(bef-left[i+1])
        bef = left[i+1]
    # print(ans)
    print(" ".join(map(str,ans[::-1])))

Submission status: Wrong Answer

Solution code:


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


class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_leaves = 2**(len(nb)-1)
        else:
            self.num_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_leaves * 2)]
        self.identity = identity
        self.operator =operator
        self.n = n

    def build(self,init_arr):
        for i in range(self.n):
            self.array[i+self.num_leaves] = init_arr[i]
        for i in range(self.num_leaves):
            pt = self.num_leaves-1-i
            self.array[pt] = self.operator(self.array[pt*2],self.array[pt*2+1])


    def update(self,x,val):
        actual_x = x+self.num_leaves
        # self.array[actual_x] = self.operator(self.array[actual_x],val)
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

    def find(self, l, r):
        #findの方が高速?
        l += self.num_leaves
        r += self.num_leaves+1
        ret = self.identity
        while l < r:
            if l & 1:
                ret = self.operator(ret, self.array[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.operator(ret, self.array[r])
            l //= 2
            r //= 2
        return ret

st = segtree(n+1,min,1e10)

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

st.build(arr)

for i in range(1,n+1):
    if s[i] == "1":
        continue
    else:
        left = max(i-m,0)
        right = i-1
        tm = st.find(left,right)
        arr[i] = tm+1
        st.update(i,tm+1)




nowm = arr[-1]

if nowm > 1e9:
    print(-1)
else:
    ans = [-1]
    for i in range(1,n+2):
        if nowm > arr[-i]:
            nowm = arr[-i]
            ans.append(-i)
        elif nowm == arr[-i]:
            ans[-1] = -i

    ans[0] = -1
    anss = ""
    for i in range(len(ans)-1):
        anss += str(ans[i]-ans[i+1])+" "
    anss = anss[:-1]
    print(anss[::-1])

Submission status: Wrong Answer

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

sl = sl[::-1]

dp = [float("inf") for _ in range(n+1)]
before = [-1 for _ in range(n+1)]
dp[0] = 0

for i in range(n):
    for j in range(1, m+1):
        if i + j <= n:
            if dp[i] + 1 <= dp[i+j] and sl[i+j] == "0":
                dp[i+j] = dp[i] + 1
                before[i+j] = i
    if dp[-1] != float("inf"):
        break


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

ansl = []
now = n
while True:
    if before[now] == -1:
        break
    ansl.append(now - before[now])
    now = before[now]

print(*ansl)

Submission status: Wrong Answer

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

x = n
roulette = []
while x > m:
    for i in range(m, 0, -1):
        if s[x-i] == '0':
            x -= i
            roulette.append(i)
            break
    else:
        print(-1)
        exit()
roulette.append(x)
roulette.reverse()
print(roulette)

Submission status: Wrong Answer

Solution code:
from bisect import *
n,m = map(int,input().split())
S = input()
ok = []
for i,s in enumerate(S):
    if s == '0':
        ok.append(i)

now = 0
ans = []
while now != n:
    nxt = ok[bisect_right(ok, now + m) - 1]
    if nxt == now:
        ans = [str(-1)]
        break
    else:
        ans.append(str(nxt - now))
        now = nxt
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r

n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()
possible = [i for i in range(n + 1) if s[i] == '0']

def main():
  trail = [0]
  cur = 0
  while True:
    if cur == n:
      break
    nxt = possible[bi_r(possible, cur + m) - 1]
    if nxt == cur:
      print(-1)
      return
    trail.append(nxt)
    cur = nxt
  
  res = [trail[i+1] - trail[i] for i in range(len(trail) - 1)]
  print(*res, sep=' ')

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos > 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos = pos-i
print(ans.strip())

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    s = input()[::-1]
    if n <= m:
        print(m)
    else:
        cnt = 0
        for i in range(n):
            if s[i] == "1":
                cnt += 1
            else:
                cnt = 0
            if cnt >= m:
                print(-1)
                exit()
        pos = 0
        res = []
        while n != pos:
            for i in reversed(range(m + 1)):
                if pos + i > n:
                    continue
                if s[pos + i] != "1":
                    pos += i
                    res.append(i)
                    break
            else:
                break
        print(*res[::-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    s = input()[::-1]
    if n <= m:
        print(m)
    else:
        cnt = 1
        for i in range(n - 1):
            if s[i] == s[i + 1] and s[i] == "1":
                cnt += 1
            else:
                cnt = 1
            if cnt >= m:
                print(-1)
                exit()
        pos = 0
        res = []
        while n != pos:
            for i in reversed(range(m + 1)):
                if pos + i > n:
                    continue
                if s[pos + i] != "1":
                    pos += i
                    res.append(i)
                    break
            else:
                break
        print(*res[::-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, m = MAP()
s = STR()
dp = [inf for _ in range(n + 1)]
dp[0] = 0
ans = []
i = n
while i > 0:
    if s[i] == '0':
        prei = i
        for j in reversed(range(1, m + 1)):
            if i - j >= 0 and s[i - j] == '0':
                dp[i - j] = dp[i] + 1
                ans.append(str(j))
                i -= j
                break
        if i == prei:
            print(-1)
            exit()
if dp[0] >= inf:
    print(-1)
    exit()
ans.reverse()
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, m = MAP()
s = STR()
dp = [inf for _ in range(n + 1)]
dp[0] = 0
ans = []
i = 0
while i < n:
    if s[i] == '0':
        prei = i
        for j in reversed(range(1, m + 1)):
            if i + j <= n and s[i + j] == '0':
                if dp[i + j]> dp[i] + 1:
                    dp[i + j] = dp[i] + 1
                    ans.append(str(j))
                    i += j
                break
        if i == prei:
            print(-1)
            exit()
if dp[n] >= inf:
    print(-1)
    exit()
print(' '.join(ans))

Submission status: Wrong Answer

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

count=0
count_1=0
count_2=0
answer=[]
ans=0

for i,s in enumerate(S):
    #print(i)
    if i==0:
        pass
    elif i==N:
        count_1+=1
        answer.append(count_1)
        #print("g")
    elif s=="0"and count_1<M-1:
        count_1+=1
        count=count_1
        count_2=0
        #print("a")
    elif s=="0" and count_1==(M-1):
        count_1+=1
        count_2=0
        answer.append(count_1)
        count=0
        count_1=count
        #print("b")
    else:
        if count_1<M-1 and count_2<M-1:
            count_1+=1
            count_2+=1
            #print("c")
        elif count_2==M-1:
            ans=-1
            #print("d")
            break
        elif count_1==M-1:
            count_2+=1
            answer.append(count)
            count_1=count_2
            count=count_1
            #print("e")
if ans==-1:
    print(-1)
else:
    print(" ".join(map(str,answer)))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, list(input())))
dp = [-1]*(n+1)
r = n
for i in reversed(range(n+1)):
  if a[i]:
    continue
  if i + m < r:
    r = i + m
    while a[r]:
      r -= 1
    if r == i:
      print(-1)
      exit(0)
  dp[i] = r
d = list()
cur = 0
while cur < n:
  d.append(dp[cur] - cur)
  cur = dp[cur]
print(*d)

Submission status: Wrong Answer

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

# Greedyに進もう

path = []
c = 0
while c < N:
    g = c+M if c+M < N else N
    for m in range(g, c, -1):
        if S[m] == 1:
            continue
        else:
            path.append(m-c)
            c = m
            break
    else:
        break

if len(path) > 0:
    print(*path[::-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
S = list(map(int, input()))[::-1]
L = []
now = 0
while now < n:
  if n - now <= m:
    L.append(n - now)
    break
  for i in range(m, 0, -1):
    if not S[now+i]:
      now += i
      L.append(i)
      break
  else:
    print(-1)
    break
print(*L[::-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
S = input()+"0"*(M+1)
dp = [float("inf")]*(N+M+1)
dp[0] = 0
for k in range(N):
    for s in range(1,M+1):
        if S[k+s] == "0":
            dp[k+s] = min(dp[k+s],dp[k]+1)

if dp[N] == float("inf"):
    print(-1)
    exit(0)
dp = dp[:N+1][::-1]
now = dp[0]-1
ans = [0]*(dp[0]+1)
for k in range(N+1):
    if dp[k] == now:
        ans[now] = k
    elif dp[k] == now - 1:
        ans[now-1] = k
        now -= 1
t = []
for k in range(1,dp[0]+1):
    t.append(ans[k-1]-ans[k])
print(*t)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    l = list(input())
    l = l[::-1]
    count = [-1]*(n+1)
    count[0] = 0
    check = 1
    i = 0

    while i < n+1:
        if count[i] != -1:
            a = -1
            for j in range(1,m+1):
                if i+j < n+1 and l[i+j] != "1":
                    count[i+j] = check
                    a = i+j
            
            check += 1
            if a == -1:
                print(-1)
                exit()
            else:
                i = a
            
            if count[-1] != -1:
                break
    count = count[::-1]

    ans = []
    a = 0
    for i in range(check-2,-1,-1):
        b = count.index(i)
        ans.append(b-a)
        a = b
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dp = [-1] * (N + M + 1)
dp[0] = 0
pos = 0

while pos < N:
    dist = dp[pos]
    tmp = pos

    for i in range(1, M + 1):
        if pos + i > N:
            break
        if S[pos + i] == "0":
            dp[pos + i] = dist + 1
            tmp = pos + i
    if pos == tmp:
        break
    pos = tmp

if dp[N] == -1:
    print(-1)
    exit()

end = dp[N]
ans = []
now = 0
for i, v in enumerate(dp):
    if now == end:
        ans.append(N)
        break
    if now == v:
        ans.append(i)
        now += 1

ans = [y - x for x, y in zip(ans[:-1], ans[1:])]
print(*ans, sep=" ")

Submission status: Wrong Answer

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

# マスiに到達する最短手数
dp = [-1] * (N + 1)
dp[0] = 0

p = 0
while p <= N:
    cnt = dp[p]
    q = p
    for i in range(1, M + 1):
        if p + i > N:
            break
        if S[p + i] == "1":
            continue
        q = p + i
        dp[q] = cnt + 1

    if p == q:
        break
    p = q

if dp[N] == -1:
    ans = [-1]
else:
    ans = []
    cnt = 0
    pos = 0
    while pos < N:
        if cnt + 1 == dp[N]:
            ans.append(N - pos)
            break
        for i in range(1, M + 1):
            if dp[pos + i] == cnt + 1:
                cnt += 1
                ans.append(i)
                pos += i
                break

print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
import copy
n, m = map(int, input().split())
s = input()
d = [[] for i in range(n+1)]
d[0] = ["0"]
for i in range(1,n+1):
  for k in range(min(i,m),0,-1):
    if s[i-k] == "0":
      d[i] = copy.deepcopy(d[i-k])
      d[i].append(str(k))
      break
if d[n]==[]:
  print(-1)
else:
  print(" ".join(d[n][1:]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()
s=s[::-1]
r,l,cnt,k,=0,0,0,0
ans=[]
while 1:
  while cnt<m:
    r+=1
    if r==n:
      ans.append(r-k)
      print(r,l)
      print(*ans[::-1])
      exit()
    if s[r]=='0':
      l=r
    cnt+=1
  if r-l==m:
    print(-1)
    exit()
  ans.append(l-k)
  k=l
  cnt=r-l

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,M = map(int,input().split())
INFTY = 10**6
S = input().strip()
S0 = []
for i in range(N+1):
    if S[i]=="0":
        S0.append(i)
flag = 0
for i in range(1,len(S0)):
    if S0[i]-S0[i-1]>M:
        flag = 1
        break
if flag==1:
    print(-1)
else:
    C = [[INFTY,-1,-1] for _ in range(N+1)]
    C[N] = [0,0,N]
    for i in range(len(S0)-2,-1,-1):
        j = S0[i]
        if N-j<=M:
            C[j] = [1,N-j,N]
        else:
            k = S0[bisect_right(S0,j+M)-1]
            a = C[k][0]
            high = k
            low = j
            while high-low>1:
                mid = S0[bisect_right(S0,(high+low)//2)-1]
                if mid==high or mid==low:
                    break
                if C[mid][0]==a:
                    high = mid
                else:
                    low = mid
            C[j] = [a+1,high-j,high]
    i = 0
    A = []
    while i<N:
        A.append(C[i][1])
        i = C[i][2]
    print(*A)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,M = map(int,input().split())
INFTY = 10**6
S = input().strip()
S0 = []
for i in range(N+1):
    if S[i]=="0":
        S0.append(i)
C = [[INFTY,-1,-1] for _ in range(N+1)]
C[N] = [0,0,N]
for i in range(len(S0)-2,-1,-1):
    j = S0[i]
    if N-j<=M:
        C[j] = [1,N-j,N]
    else:
        ind = bisect_right(S0,j+M)-1
        k = S0[ind]
        if k==j:
            break
        a = C[k][0]
        high = k
        low = j
        while high-low>1:
            mid = S0[bisect_right(S0,(high+low)//2)-1]
            if mid==high or mid==low:
                break
            if C[mid][0]==a:
                high = mid
            else:
                low = mid
        C[j] = [a+1,high-j,high]
if C[0][0]==INFTY:
    print(-1)
else:
    i = 0
    A = []
    while i<N:
        A.append(C[i][1])
        i = C[i][2]
    print(*A)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N,M = map(int,input().split())
INFTY = 10**6
S = input().strip()
S0 = []
for i in range(N+1):
    if S[i]=="0":
        S0.append(i)
C = [[INFTY,-1,-1] for _ in range(N+1)]
for i in range(len(S0)-1,-1,-1):
    j = S0[i]
    if N-j<=M:
        C[j] = [1,N-j,N]
    else:
        ind = bisect_right(S0,j+M)-1
        k = S0[ind]
        if k==j:
            break
        a = C[k][0]
        high = k
        low = j
        while high-low>1:
            mid = (high+low)//2
            if C[mid][0]==a:
                high = mid
            else:
                low = mid
        C[j] = [a+1,high-j,high]
if C[0][0]==INFTY:
    print(-1)
else:
    i = 0
    A = []
    while i<N:
        A.append(C[i][1])
        i = C[i][2]
    print(*A)

Submission status: Wrong Answer

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

if N == 1:
    print(1)
    exit()

dp = [None for _ in range(N+1)]
dp[0] = 0

for i in range(1, N+1):
    if S[i] == '1':
        continue
    else:
        prv_dp_val = dp[i]
        for j in range(1, M+1):

            if dp[i-j] is not None:
                if dp[i] is None:
                    dp[i] = i - j
                else:
                    dp[i] = min(dp[i], i - j)
                    break

if dp[-1] is None:
    print(-1)
else:
    ans = []
    idx = N
    while idx > 0:
        ans.append(idx - dp[idx])
        idx = dp[idx]
    print(*ans[::-1])

Submission status: Wrong Answer

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

# 現在位置
now = 0
_now = 0
ans = []
while now <= N-1:
    for i in range(min(M, N-now), 0, -1):
        if S[now+i] == '0':
            ans.append(i)
            now += i
            break
    if _now == now:
        print(-1)
        exit()
    _now = now

# 辞書順最小化を目指す
ans = sorted(ans)
new_ans = []
now = 0
while len(ans) > 0:
    for a in ans:
        if S[now+a] == '0':
            new_ans.append(a)
            ans.remove(a)
            now += a
            break
print(*new_ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(n) for n in input().split()]
S = input()

ans = []
s = M
l = N
while True:
    if s >= l:
        ans.insert(0, l)
        break
    if S[l-s] == "1":
        if s == 1:
            break
        s -= 1
        continue
    l -= s
    ans.insert(0, s)
    s = M

if len(ans) == 0:
    print(-1)
else:
    print(" ".join([str(n) for n in ans]))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    S = input()[::-1]
    
    s = 0
    ans = []
    
    while s < N:
        
        for i in range(M, -1, -1):
            if s+i > N: continue
            if S[s+i] == '0': break
            
        if not i: 
            print(-1)
            sys.exit()
        ans.append(i)
        s += i
    print(' '.join(map(str, ans[::-1])))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = input()[::1]
print(s)
now = 0
L = []
while now<n:
  t = s[now:now+m+1].rfind("0")
  print(t, now, now+m+1, s[now:now+m+1])
  if t==0:
    print(-1)
    exit()
  else:
    L.append(t)
    now += t
print(*L[::1])

Submission status: Wrong Answer

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

from collections import deque
q = deque()

pre = [-1] * (n+1)
f = [float('inf')] * (n +1)
f[0] = 0

q.append((f[0], 0))
for i in range(1, n+1):
  while q and i - q[0][1] > m:
    q.popleft()
  if s[i] == '1': continue
  if q:
    f[i] = q[0][0] + 1
    pre[i] = q[0][1]
  while q and q[-1][0] > f[i]:
    q.pop()
  q.append((f[i], i))

if pre[n] == -1:
  print(-1)
else:
  now = n
  res = [n]
  while pre[now] != -1:
    now = pre[now]
    res.append(now)
  res = res[::-1]
  ans = [y -x for x, y in zip(res, res[1:])]
  print(*ans)

Submission status: Wrong Answer

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

from collections import deque
q = deque()

pre = [-1] * (n+1)
f = [float('inf')] * (n +1)
f[0] = 0

q.append((f[0], 0))
for i in range(1, n+1):
  while q and i - q[0][1] > m:
    q.popleft()
  if s[i] == '1': continue
  if q:
    f[i] = q[0][0] + 1
    pre[i] = q[0][1]
  while q and q[-1][0] > f[i]:
    q.pop()
  q.append((f[i], i))

if pre[n] == -1:
  print(-1)
else:
  now = n
  res = [n]
  while pre[now] != -1:
    now = pre[now]
    res.append(now)
  res = res[::-1]
  for x, y in zip(res, res[1:]):
    print(y-x)