Problem:


Score : 600 points

Problem Statement

Takahashi is playing a board game called Sugoroku.

On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.

The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.

Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.

Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^5

|S| = N + 1

S consists of 0 and 1.

S[0] = 0

S[N] = 0

Input

Input is given from Standard Input in the following format:

N M
S

Output

If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.

If Takahashi cannot win the game, print -1.

Sample Input 1

9 3
0001000100

Sample Output 1

1 3 2 3

If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.

Sample Input 2

5 4
011110

Sample Output 2

-1

Takahashi cannot reach Square 5.

Sample Input 3

6 6
0101010

Sample Output 3

6



Sample input:
9 3
0001000100


Sample output:
1 3 2 3

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()

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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=min(seg[2*i+1],seg[2*i+2]) 

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = inf

ans=inf

s=[int(i) for i in input()]

def dp(b,m): # N log (N)
    N=len(b)-1
    n=N+1
    global seg
    global num
    
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    init([inf]*n)
    
    update(0,0)

    dp=[0]+[inf]*(N)
    for i in range(N):
        if b[i+1]==1:
            continue
        dp[i+1]=query(max(i-m+1,0),i+1)+1
        update(i+1,dp[i+1])
        #show(seg)
        #show(dp)
    return dp

dp1=dp(s,m)
step=dp1[n]
if step==inf:
    print(-1)
    exit()

dp2=dp(s[::-1],m)[::-1]

move=[0]
ans=[]
j=1
for i in range(step,0,-1): # N
    while j<=n and dp2[j]!=i-1:
        j+=1
    #ans.append(j-move[-1])
    move.append(j)

# 2 * N log N + N
'''
show(s)
show(dp1,step)
show(dp2)
show(move)
'''

for i in range(len(move)-1):
    ans.append(move[i+1]-move[i])
print(*ans)

Submission status: Accepted

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

now = n
res = []

while now != 0:
    judge = False
    for i in range(max(0,now-m),now):
        if s[i] == '0':
            res.append(now-i)
            now = i
            judge = True
            break
    if not judge:
        print(-1)
        exit()
for i in range(len(res)-1,-1,-1):
    print(res[i],end = ' ')

Submission status: Accepted

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

s = input()
c = n

h = []
while True:
	d = m
	while d > 0:
		if c - d >= 0:
			if s[c - d] == '0':
				break
		d -= 1

	if d == 0:
		print(-1)
		break
	
	c -= d
	h.append(str(d))
	if c == 0:
		h.reverse()
		print(' '.join(h))
		break

Submission status: Accepted

Solution code:
import sys

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

S = input()

slis = list(S)
slis.reverse()

ans = []

now = 0
#print (slis)

while now != N:

    flag = False

    for i in range(M):
        i = M - i

        if now + i <= N and slis[now + i] == "0":
            flag = True
            now = now + i
            ans.append(i)
            break

    if not flag:
        print (-1)
        sys.exit()

ans.reverse()

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
if '1' * m in s:
    print(-1)
else:
    p = n
    t = []
    while p > 0:
        for r in range(m, 0, -1):
            if p - r >= 0 and s[p - r] == '0':
                t.append(r)
                p -= r
                break
    print(" ".join([str(r) for r in reversed(t)]))

Submission status: Accepted

Solution code:
class segment_tree_dual:
    def __init__(self, N, compose, funcval, ID_M=None):
        self.compose = compose
        self.ID_M = ID_M
        self.funcval = funcval

        self.height = (N-1).bit_length() #木の段数
        self.N0 = 1<<self.height #木の横幅 >= N
        self.laz = [self.ID_M]*(2*self.N0) #作用素の木
        self.val = None #値の配列

    #初期値の配列を作る
    def build(self,initial):
        self.val = initial[:]

    #laz[k] を子に伝える、k が一番下の場合は laz[k] を val に反映する
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        if self.N0 <= k:
            self.val[k-self.N0] = self.funcval(self.val[k-self.N0], self.laz[k])
            self.laz[k] = self.ID_M
        else:
            self.laz[(k<<1)  ] = self.compose(self.laz[(k<<1)  ],self.laz[k]);
            self.laz[(k<<1)+1] = self.compose(self.laz[(k<<1)+1],self.laz[k]);
            self.laz[k] = self.ID_M;
    
    # 遅延をすべて解消する
    def propagate_all(self):
        upto = self.N0 + len(self.val)
        for i in range(1,upto): self.propagate(i)

    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, L,R,f):
        L += self.N0; R += self.N0+1
        """まず伝播させる（オペレータが可換なら必要ない）"""
        #self.thrust(L)
        #self.thrust(R-1)
        #登りながら関数 f を合成
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R],f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L],f)
                L += 1
            L >>= 1; R >>= 1
    
    # values[k] を取得。
    def point_get(self, k):
        res = self.val[k]
        k += self.N0
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k //= 2
        return res
    
    # values[k] = x 代入する
    def point_set(self, k): 
        self.thrust(k+self.N0)
        self.val[k] = x

###########################################################################
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n,m = [int(i) for i in readline().split()]
s = input()[::-1]

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

compose = min
funcval = min
ID_M = INF = 10**18

seg = segment_tree_dual(n, compose, funcval, ID_M)
seg.build([0]+[INF]*(n))

for i in range(n):
    if s[i] == "1": seg.val[i] = -1
    else:
        v = seg.point_get(i)
        #print(v,i)
        seg.update(i+1,min(n,i+m),v+1)
        #print(seg.laz)

seg.propagate_all()
#print(s)
#print(seg.val)

val = seg.val
if val[-1] == -1 or val[-1] == INF:
    print(-1)
    exit()

ans = []

now = n
time = val[-1]
while now:
    n2 = now-1
    time -= 1
    while s[n2] == "1" or val[n2] != time:
        n2 -= 1
    ans.append(now-n2)
    now = n2
    
print(*ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
flag = True
for i in range(n - m + 2):
    if s[i:i + m] == "1" * m:
        flag = False
        break
if flag == False:
    print(-1)
else:
    dice = []
    step = 0
    while step < n:
        if step + m > n:
            dice.append(n - step)
            break
        else:
            dice2 = m
            while s[-step - 1 - dice2] == "1":
                dice2 -= 1
            else:
                step += dice2
                dice.append(dice2)
    dice.reverse()
    dice = [str(dice[i]) for i in range(len(dice))]
    print(" ".join(dice))

Submission status: Accepted

Solution code:
def main():
    n, m = [int(x) for x in input().split()]
    s = input()
    c = n
    h = []
    while(True):
    	d = m
    	while d > 0:
    		if c - d >= 0:
    			if s[c - d] == '0':
    				break
    		d -= 1
    
    	if d == 0:
    		print(-1)
    		break
    	
    	c -= d
    	h.append(str(d))
    	if c == 0:
    		h.reverse()
    		print(' '.join(h))
    		break
main()

Submission status: Accepted

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

s = input()
c = n

h = []
while True:
	d = m
	while d > 0:
		if c - d >= 0:
			if s[c - d] == '0':
				break
		d -= 1

	if d == 0:
		print(-1)
		break
	
    
    
	c -= d
	h.append(str(d))
	if c == 0:
		h.reverse()
		print(' '.join(h))
		break

Submission status: Accepted

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

p = 0
ans = []
while p < n:
    b = p
    p += k
    if p > n:
        ans.append(str(n-b))
        break
    while s[p] == 1:
        p -= 1
    if p == b:
        print(-1)
        exit()
    ans.append(str(p-b))

print(' '.join(reversed(ans)))

Submission status: Accepted

Solution code:
import bisect

n, m=(int(i) for i in input().split())
s=input()
alist=[]
for i in range(n+1):
    if s[i]=='0':
        alist.append(i)

now=n
swit=0
dame=0
root=[]
while swit==0:
    koho=max(0, now-m)
    #print(alist, koho)
    bango=bisect.bisect_left(alist, koho)
    tugi=alist[bango]
    if now==tugi:
        swit=1
        dame=1
    elif tugi==0:
        swit=1
    root.append(now-tugi)
    now=tugi

if dame==1:
    print(-1)
else:
    newt=[]
    for i in range(len(root)):
        #newt.append(root[len(root)-i-1])
        if i!=len(root)-1:
            print(root[len(root)-i-1], end=" ")
        else:
            print(root[len(root)-i-1])
    #print(newt)

Submission status: Accepted

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

for i in range(n-1, -1, -1):
    if s[i] == '1':
        dp[i] = -1
        continue
    while(r > i + m):r -= 1
    while(dp[r] == -1): r-= 1
    if i == r:
        print(-1)
        exit(0)
    dp[i] = dp[r] + 1

now = 0
ans = []
for i in range(n+1):
    if dp[i] == -1: continue
    if dp[i] != dp[now]:
        ans.append(i-now)
        now = i

print(*ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    s = input()
    s = s[::-1]
    dp = [float("inf")]*(n+1)
    dp[0] = 0
    q = deque([0])
    ans = []
    f = [0]*(n+1)
    for i in range(n+1):
        if s[i] == "1":
            f[i] = f[i-1]
        else:
            f[i] = i
    while q:
        x = q.popleft()
        r = min(n,x+m)
        y = f[r]
        if x == y:
            break
        dp[y] = dp[x]+1
        q.append(y)
        ans.append(y-x)
    if dp[n] == float("inf"):
        print(-1)
        return
    print(*ans[::-1])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
l = list(map(int,list(input()[::-1])))
safe = [-1]*(n+1)
r = n
for i in range(n,-1,-1):
    if l[i]:
        continue
    if r-i > m:
        r = i+m
        while l[r]:
            r -= 1
        if r == i:
            print(-1)
            exit()
    safe[i] = r
dice = list()
cur = 0
while cur < n:
    dice.append(safe[cur]-cur)
    cur = safe[cur]
print(" ".join(map(str,dice[::-1])))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
s = s[::-1]
place = 0
res = []
while place < n:
  sub_s = s[place+1:place+m+1]
  if "0" in sub_s:
    dist = len(sub_s) - sub_s[::-1].index("0")
  else:
    print(-1)
    exit()
  place += dist
  res.append(str(dist))
print(" ".join(res[::-1]))

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve(n, m, s):
    i = n
    res_list = []
    while i > 0:
        flag = True
        for j in range(min(i, m), 0, -1):
            if s[i - j] == "0":
                res_list.append(j)
                i -= j
                flag = False
                break
        if flag:
            return [-1]
    return list(reversed(res_list))


def main():
    n, m = map(int, input().split())
    s = input()
    res_list = solve(n, m, s)
    print(*res_list)


def test():
    assert solve(9, 3, "0001000100") == [1, 3, 2, 3]
    assert solve(5, 4, "011110") == [-1]
    assert solve(6, 6, "0101010") == [6]


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def solve(n, m, s):
    curr = n
    l = max(0, n - m)
    r = n
    ans = []
    while r > 0:
        for i, c in enumerate(s[l:r], start=l):
            if c == '0':
                dice = curr - i
                ans.append(dice)
                curr = i
                l = max(0, i - m)
                r = i
                break
        else:
            return (-1,)

    return reversed(ans)


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

Submission status: Accepted

Solution code:
class SegmentTree:#抽象セグ木
    def __init__(self, N, id, fun):#id:単位元
        self.N0 = 2**(N-1).bit_length()
        self.id = id
        self.data = [(inf, i)for i in range(2*self.N0)]
        self.fun = fun
    def update(self, k, x):
        k+=self.N0-1
        self.data[k] = x
        while k>=0:
            k = (k-1)//2
            self.data[k] = self.fun(self.data[2*k+1], self.data[2*k+2])
    def query(self, l, r):#[l, r)
        L = l+self.N0; R = r+self.N0
        s = self.id
        while L<R:
            if R&1:
                R-=1
                s = self.fun(s, self.data[R-1])
            if L&1:
                s = self.fun(s, self.data[L-1])
                L+=1
            L >>= 1; R>>=1
        return s
inf = float('inf')
N, M = map(int, input().split())
S = input()
dp = [0]*(N+1)
seg = SegmentTree(N+1, (inf, inf), min)
seg.update(0, (0, 0))
for i in range(1, N+1):
    if S[i] == '1':
        dp[i] = (inf, -1)
    else:
        c, j = seg.query(max(0, i-M), i)
        if c == inf:
            dp[i] = (inf, -1)
        dp[i] = (c+1, j)
        seg.update(i, (c+1, i))
if dp[-1][0] == inf:
    print(-1)
else:
    i = N
    ans = []
    while i>0:
        j = dp[i][1]
        ans.append(i-j)
        i = j
    print(*ans[::-1])

Submission status: Accepted

Solution code:
from bisect import bisect_left
N, M = map(int, input().split())
S = input()
mass = []
for i, c in enumerate(S):
    if c == '0':
        mass.append(i)

dp = [None] * (N+1)
dp[0] = (0, 0)
for i in range(1, N+1):
    if S[i] == '0':
        x = bisect_left(mass, i - M)
        idx = mass[x]
        if idx >= i:
            print(-1)
            exit()
        dp[i] = (dp[idx][0]+1, i - idx)

now = N
ans = []
while now > 0:
    ans.append(dp[now][1])
    now -= dp[now][1]
print(' '.join(map(str, reversed(ans))))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    S=list(input())
    S=list(map(int,S))[::-1]
    ans=[]
    now=0
    while(now<n):
        next=now
        for i in range(1,m+1):
            if(now+i==n):
                next=n
                break
            if(S[now+i]==0): next=now+i
        if(now==next):
            print(-1)
            return
        ans.append(next-now)
        now=next
    ans=ans[::-1]
    print(*ans)
resolve()

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
masu=list(map(int,input()))
i=0
m=[]
while i<len(masu)-1:
  k=masu.index(0,i+1)-i
  m+=[k]
  i+=k
if max(m)>b:print(-1)
else:
  i=len(m)-1
  while i:
    if m[i]+m[i-1]<=b:
      m[i]+=m[i-1]
      del m[i-1]
    i-=1
  print(' '.join(map(str,m)))

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    S=ST()
    ans_rev = []
    S_rev = S[::-1]
    i=0
    while i<N:
        step = False
        for j in range(1,M+1)[::-1]:
            if i+j>N:
                continue
            if S_rev[i+j]=="0":
                step=True
                ans_rev.append(j)
                i += j
                break
        if not step:
            print(-1)
            exit()
    print(*ans_rev[::-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(N-1,0,-1):
    if S[i]>0:
        S[i] = S[i+1]+1

ans = []
j = N
while j>0:
    k = max(0,j-M)
    while k<j:
        if S[k] == 0:
            ans.append(j-k)
            j = k
            break
        else:
            k += S[k]
    else:
        ans = [-1]
        break
print(*ans[::-1])

Submission status: Accepted

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

D = []
t = N
while t > 0:
  if t - M <= 0:
    D.append(t)
    break
  for i in range(M, 0, -1):
    if S[t - i] == "0":
      D.append(i)
      t -= i
      break
  else:
    print(-1)
    exit()

for i in range(len(D) -1, -1, -1):
  print(D[i],end = " ")

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
s = ns()

def make(s, m):
    n = len(s)-1
    ldp = [99999999] * (n+1)
    ldp[0] = 0
    p = 0
    for i in range(1, n+1):
        if s[i] == "1":
            continue
        while p + m < i or s[p] == "1":
            p += 1
        if p >= i:
            print(-1)
            sys.exit(0)
        ldp[i] = ldp[p] + 1
    return ldp

dp = make(s, m)
rdp = make(s[::-1], m)

pre = 0
prex = 0
for i in range(n+1):
    if s[i] == "0":
        if pre < dp[i] and dp[i] + rdp[n-i] == dp[n]:
            sys.stdout.write(str(i-prex))
            sys.stdout.write(" ")
            prex = i
            pre = dp[i]

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()
S = list(map(int,list(input())))

cnt = 1
tmp = []
for i in range(1,N+1):
    if S[i] == 0:
        if cnt > M:
            print(-1)
            exit()
        tmp.append(cnt)
        cnt = 1
    else:
        cnt += 1


cnt = 0
ans = []
for d in reversed(tmp):
    if cnt + d <= M:
        cnt += d
    else:
        ans.append(cnt)
        cnt = d

ans.append(cnt)
ans.reverse()

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

Submission status: Accepted

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

cur = N
while cur > 0:
  prevC = cur
  cur = max(0,cur-M)
  while S[cur]=='1':
    cur+=1;
  if cur==prevC:
    print(-1)
    exit(0)
  arr.append(str(prevC-cur))
arr.reverse()
print(' '.join(arr))

Submission status: Accepted

Solution code:
class SegmentTree():
    """区間更新、一点取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: 区間[begin, end)をvalに更新する
    get_val: i番目の値を求める
    """
    def __init__(self, n):
        self.update_cnt = 0
        self.n = n
        self.size = 1
        INF = 2**32 - 1
        while self.size < n:
            self.size *= 2
        self.node = [(self.update_cnt, -1) for i in range(2*self.size - 1)]

    def update(self, begin, end, val):
        self.update_cnt += 1
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = (self.update_cnt, val)
            if (begin - 1) & 1:
                self.node[begin] = (self.update_cnt, val)
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = max(val, self.node[i])
        return val[1]


n, m = map(int, input().split())
s = input()
st = SegmentTree(n+1)

for i in range(n+1)[::-1]:
    if s[i] == "0":
        st.update(i+1, min(i+1+m,n+1) , i)

pos = []
start = n
while True:
    if start == 0:
        break
        
    tmp = st.get_val(start)
    if tmp == -1:
        print(-1)
        exit()
    pos.append(start - tmp)
    start= tmp
print(*pos[::-1])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# (回数、インデックス)をheapで管理

from heapq import heappop, heappush

N,M = map(int,readline().split())
S = [x - ord('0') for x in read().rstrip()]

INF = 10 ** 18
dp_cnt = [INF] * (N+1)
dp_next = [0] * (N+1)

dp_cnt[N] = 0
q = [(0,N)]

for n in range(N-1,-1,-1):
    while True:
        cnt,ind = q[0]
        if ind > n + M:
            heappop(q)
            continue
        break
    cnt += 1
    if S[n] == 1:
        cnt = INF
        ind = 0
    dp_cnt[n] = cnt
    dp_next[n] = ind
    heappush(q, (cnt, n))

if dp_cnt[0] >= INF:
    print(-1)
    exit()

answer = []
append = answer.append
x = 0
while x != N:
    y = dp_next[x]
    append(y-x)
    x = y

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

Submission status: Accepted

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

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

ANS=[]

NOW=N
while NOW!=0:
    for i in range(M,0,-1):
        if NOW-i>=0 and S[NOW-i]=="0":
            NOW-=i
            ANS.append(i)
            break
    else:
        print(-1)
        sys.exit()

print(*ANS[::-1])

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_f
# F - Sugoroku

def search(a,x,ans):
    if x==0:
        #ans_list.append(ans)
        final=ans[::-1]
        ret=[]
        for i in range(1,maxi+1):
            ret.append(final[i]-final[i-1])
        print(*ret)
        sys.exit()
    else:
        target=L[x-1]
        for p in target:
            if a-p<=M:
                ret=search(p,x-1,ans+[p])                

import sys
N,M = map(int,input().split())
S=list(input())
#print(S)

dp=[float("inf")]*(N+1)
dp[0]=0

for i in range(1,N+1):
    if S[i]=="1":
        pass
    else:
        for j in range(1,M+1):
            if i>=j:
                if S[i-j]=="0":
                    tmp= dp[i-j]+1
                    dp[i]=min(tmp,dp[-1])
#print(dp)
if dp[-1]==float("inf"):
    print(-1)
else:
    ans_list=[]
    maxi=dp[-1]
    L=[ [] for _ in range(maxi+1)]
    for i,num in enumerate(dp):
        if num!=float("inf"):
            L[num].append(i)
    #print(L)
    search(N,maxi,[N])
    #print(ans_list)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n, m = list(map(int, input().split(' ')))
routes = [int(i) for i in input()]
ans = []
min_length = 9999999999999
def f(current, history):
    global ans
    global min_length
    # todo: 多分TLEなのでここで history ごとメモってしまう？
    
    if current >= n:
        if current == n:
            if len(history) < min_length:
                ans = history[:]
                min_length = len(ans)
            if len(history) == min_length:
                if ''.join([str(z) for z in ans]) > ''.join(str(z) for z in history):
                    ans = history[:]
        return -1
    for i in range(1, m+1):
        if current + i >= len(routes) or routes[current + i]:
            continue
        f(current + i, history + [i])
f(0, [])

print(' '.join(ans) if ans != [] else -1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


@mt
def slv(N, M, S):

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dfs(x):
        if x == 0:
            return []

        for i in range(M, 0, -1):
            if 0 <= x-i and S[x-i] == '0':
                r = dfs(x-i)
                if r is not None:
                    r.append(i)
                    return r
        return None
    ans = dfs(N)
    if ans is None:
        ans = [-1]
    return ans




def main():
    N, M = read_int_n()
    S = read_str()
    print(*slv(N, M, S))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dp=[[] for _ in range(N+1)]
dp[0]=(0,[])
for i in range(1,N+1):
  if S[i]==0:
    cand=[]
    for j in range(1,M+1):
      if S[i-j]==1:
        continue
      elif i-j<0:
        break
      cand.append((dp[i-j][0]+1,dp[i-j][1]+[j]))
    cand.sort()
    #print(i,cand)
    if cand:
      dp[i]=cand[0]
    
#print(dp)
if dp[-1]:
  print(*dp[-1][1])
else:
  print(-1)

Submission status: Runtime Error

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

if M >= N:
    print(N)
    exit()

p = -1
for i in reversed(range(1,M+1)):
    if S[i] == "0":
        p = i
        break

if p == -1:
    print(-1)
    exit()
print(p)
ps = [p]
for _ in range(N//M):
    tmp = -1
    for i in reversed(range(ps[-1]+1,ps[-1]+M+1)):
        try:
            if S[i] == "0":
                ps.append(i)
                tmp = i
                break
        except:
            pass
    if tmp == -1:
        print(-1)
        exit()
pp = [ps[i+1]-ps[i] for i in range(len(ps)-1)]
print(*pp[::-1],ps[0])

Submission status: Runtime Error

Solution code:
import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  count = 0
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    if s1 < count:
      continue
    count = s1+1
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (count, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()