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 collections import defaultdict
import bisect

#入力受け取り
def getlist():
	return list(map(int, input().split()))

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

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

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache
setrecursionlimit(10**6)
input=stdin.readline

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

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

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

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

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

    ans = []

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

    ans.reverse()

    print(" ".join(ans))





if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

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

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

def check(a):
    for i in range(min(N, a+M), a, -1):
        if S[i] == '0':
            return i
    return a

i = 0
ans = []
while i < N:
    res = check(i)
    if res == i:
        print(-1)
        exit()
    ans.append(res-i)
    i = res
print(*ans[::-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
r=[]
p=N
while p>0:
    try:
        n=p-max(0,p-M)-S[max(0,p-M):p].index('0')
    except:
        print(-1)
        exit()
    r.append(n)
    p-=n
print(*r[::-1])

Submission status: Accepted

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

ans = []

i = n
while i > 0:
    flag = 1
    for l in reversed(range(1, m+1)):
        ni = i - l
        if ni < 0:
            continue
        if s[ni] == '1':
            continue
        if s[ni] == '0':
            ans.append(l)
            i = ni
            flag = 0
            break
    if flag:
        print(-1)
        exit()

ans_ = []
for i in reversed(range(len(ans))):
    ans_.append(ans[i])
print(*ans_)

Submission status: Accepted

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

able = True
turn = []
ptr = n
searched = 0
while ptr != 0:
  goto = 0
  for i in range(1+searched, m+1):
    if ptr - i == 0:
      goto = i
      break
    elif s[ptr-i] == '0':
      goto = i
  if goto == 0:
    able = False
    break
  else:
    turn.append(goto)
    ptr -= goto
    searched = m - goto
#  print ('GOTO=' + str(goto), 'PTR=' + str(ptr))

if able:
  while len(turn):
    print(turn.pop())
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
pos=n
p=n
tmp=n
ans=[]
while pos>0:
    q=p
    while pos-q<m and q>0:
        q-=1
        #print(q)
        if s[q]=='0':
            tmp=q
    p=q
    #print()
    if tmp>=pos:
        print(-1)
        exit(0)
    ans.append(pos-tmp)
    pos=tmp
#print()
for i in range(1,1+len(ans)):
    print(ans[-i],end=' ')

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  s=S()

  ans=[]
  counter=1
  for x in s[1:]:
    if x=='0':
      if counter>m:
        return -1
      ans.append(counter)
      counter=1
    else:
      counter+=1

  ans.reverse()
  _ans=[]

  sm=0
  for x in ans:
    if sm+x>m:
      _ans.append(sm)
      sm=x
    else:
      sm+=x
  if sm>0:
    _ans.append(sm)

  _ans.reverse()
  return ' '.join([str(x) for x in _ans])


# main()
print(main())

Submission status: Accepted

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

ans = []

i = 0
j = m
while i+j>i:
    if i+j >= n:
        ans.append(n-i)
        i = n
        break
    elif i == n:
        break
    elif s[i+j] == '1':
        j -= 1
    else:
        ans.append(j)
        i += j
        j = m

if i != n:
    print(-1)
else:
    ans.reverse()
    print(*ans)

Submission status: Accepted

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

ans = []
flg = 1
i = N
while i != 0:
    for j in range(min(M, i), 0, -1):
        if S[i-j] == '0':
            ans.append(j)
            i -= j
            break
    else:
        flg = -1
        i = 0
    # print(i)

if flg == -1:
    print(flg)
else:
    ans.reverse()
    print(*ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
S = list(input())
S.reverse()
p = 0
ans = []
while p != N:
    hoge = 0
    for i in range(min(M,N-p),0,-1):
        if S[p + i] == '0':
            hoge = i
            break
    p += hoge
    if hoge == 0:
        print(-1)
        exit()
    ans.append(hoge)
print(*reversed(ans))

Submission status: Accepted

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
(N,M) = (int(i) for i in input().split(" "))
S = input()[::-1]
T = []
for s in S:
	if len(T)%2 == 0:
		if s == '0':
			T.append(1)
		else:
			T[-1]+=1
	else:
		if s== '1':
			T.append(1)
		else:
			T[-1]+=1
for i in range(1,len(T)):
	T[i] += T[i-1]
# print(T)
ans = []
cur = 0

tt = 0

while cur+M<N:
	cur += M
	while T[tt] <= cur:
		tt += 1
	if tt % 2 == 1:
		tt  -= 1
		st = M-cur+T[tt]-1
		if st == 0:
			ans = None
			break
		ans.append(st)
		cur = T[tt] - 1
	else:
		ans.append(M)
if ans != None and cur < N:
	ans.append(N-cur)
if ans == None:
	ans= [-1]
print(" ".join([str(i) for i in ans[::-1]]))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline

N, M = map(int, input().split())
S = list(input())[: -1]
x = N
res = []
s = []
for i in range(N + 1):
  if S[i] == "0": s.append(i)
#print(s)
for _ in range(N):
  if x == 0:
    break
  n = bl(s, x - M)
  #print(n)
  res.append(x - s[n])
  x = s[n]
res.reverse()
if x != 0: print(-1)
else:
  print(" ".join(list(map(str, res))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

n,m=map(int,input().split())
S=input()
step=[]
def dfs(node):
    for i in range(m,0,-1):
        if node-i<0:
            continue
        # print(S[node-i])
        if S[node-i]=="0":
            # print(12345678)
            step.append(i)
            dfs(node-i)
            return

dfs(n)
step=step[::-1]
if sum(step)!=n:
    print(-1)
else:
    print(*step)

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    s = list(input())
    sap = s.append
    _ = s.pop(-1)
    ans = []
    while True:
        x = []
        sl = len(s)
        xap = x.append
        f = False
        for i in range(m):
            if s:
                xap(s.pop(-1))
            else:
                f = True
                break
        if f:
            ans.append(sl)
            break
        lx = len(x)
        stop = 0
        g = False
        amari = []
        for i in range(lx):
            y = x.pop(-1)
            if y == "0":
                stop = m-i
                g = True
                break
            else:
                amari.append(y)
        if g:
            for i in range(len(amari)):
                sap(amari.pop(-1))
            ans.append(stop)
            if not s:
                break
        else:
            ans = -1
            break
    if ans == -1:
        print(ans)
    else:
        print(" ".join([str(i) for i in list(reversed(ans))]))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    S = input()[::-1]
    cur = 0
    i = 1
    ans = []
    while cur < N:
        cand = 0
        while i <= M and cur + i <= N:
            if S[cur + i] == "0":
                cand = i
            i += 1
        if cand == 0:
            print(-1)
            return
        ans.append(cand)
        i -= cand + 1
        cur += cand
    print(*ans[::-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class SegTree(object):
    # 区間の中で v 以下の値のうち最も左にある値と index を取得
    # 普通のセグ木に get_threshold_left と get_threshold_left_all を加えただけ
    # 検証1: https://atcoder.jp/contests/arc038/submissions/6933949 (全区間のみ)
    # 検証2: https://atcoder.jp/contests/arc046/submissions/7430924 (全区間のみ)
    # 抽象化したい
    __slots__ = ["elem_size", "tree", "default", "op"]
    def __init__(self, a: list, default=float("inf"), op=min):
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op
        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def get_threshold_left(self, x, y, v):
        # 区間 [x, y) 内で一番左の v 以下の値
        tree, result, op, elem_size = self.tree, self.default, self.op, self.elem_size
        l, r = x + elem_size, y + elem_size
        idx_left = idx_right = -1  # 内部 index
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                if idx_left == -1 and tree[l] <= v:
                    idx_left = l
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
                if tree[r] <= v:
                    idx_right = r
            l, r = l >> 1, r >> 1
        if idx_left==idx_right==-1:
            return -1, -1
        idx = idx_left if idx_left!=-1 else idx_right
        while idx < elem_size:
            idx <<= 1
            if tree[idx] > v:
                idx += 1
        return tree[idx], idx-elem_size

    def get_threshold_left_all(self, v):
        # 全区間で一番左の v 以下の値
        tree, op, elem_size = self.tree, self.op, self.elem_size
        if tree[1] > v:
            return -1, -1
        idx = 1
        while idx < elem_size:
            idx <<= 1
            if tree[idx] > v:
                idx += 1
        return tree[idx], idx-elem_size

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

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



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

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

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]


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

seg = segment_tree_dual(n+1, 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() 

N += 1
# Max size of tree  
tree = [0] * (2 * N);  
n = N
# function to build the tree  
def build() : 
  
    # insert leaf nodes in tree  
    for i in range(N) :  
        tree[n + i] = (float('inf'), float('inf'));  
      
    # build the tree by calculating parents  
    for i in range(n - 1, 0, -1) :  
        tree[i] = min(tree[i << 1], tree[i << 1 | 1])
  
# function to update a tree node  
def updateTreeNode(p, value) :  
      
    # set value at position p  
    tree[p + n] = (value, p);  
    p = p + n;  
      
    # move upward and update parents  
    i = p; 
      
    while i > 1 : 
          
        tree[i >> 1] = min(tree[i], tree[i ^ 1]);  
        i >>= 1;  
  
# function to get sum on interval [l, r)  
def query(l, r) :  
  
    res = (float('inf'), float('inf'));  
      
    # loop to find the sum in the range  
    l += n; 
    r += n; 
      
    while l < r : 
      
        if (l & 1) : 
            res = min(res, tree[l]);  
            l += 1
      
        if (r & 1) : 
            r -= 1; 
            res = min(res, tree[r]);  
              
        l >>= 1; 
        r >>= 1
      
    return res;

par = [None for i in range(N)]
build()
updateTreeNode(0, 0)
for i in range(1, N):
    if s[i] == "1": continue
    r = query(max(0, i - M), i)
    par[i] = r[1]
    updateTreeNode(i, r[0]+1)
    # updateTreeNode(i, query(max(0, i - M), i))
    
    # for k in range(1, M+1):
    #     if i - k < 0: break
    #     dp[i] = min(dp[i], (dp[i-k][0], (i - k)))



moves = []
cur = N - 1
if par[cur] == float('inf'):
    print(-1)
    quit()
try:
    while par[cur] != None:
        new = par[cur]
        moves.append(cur - new)
        cur = new
except:
    print(-1)
    quit()

moves = list(reversed(moves))
print(" ".join(map(str, moves)))

Submission status: Accepted

Solution code:

"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

from operator import eq

N,M = map(int,input().split())
N += 1
S = tuple(map(lambda x: x == '0', input()))

dp = SegmentTree.all_identity(min, eq, float('inf'), N)
dp[N-1] = 0

for i in reversed(range(N-1)):
    if S[i]:
        dp[i] = dp[i+1:min(N,i+M+1)]+1
if dp[0] == float('inf'):
    print(-1)
    exit()

res = []
i = 0
while i < N-1:
    t = dp[i]
    k = 1
    while dp[i+k] != t-1:
        k += 1
    res.append(k)
    i += k
print(*res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  _, m = map(int, input().split())
  traps = [v == '1' for v in input().strip()]
  values = [None] * len(traps)
  values[0] = -1

  for i in range(len(values) - 1):
    if values[i] is None:
      continue

    for j in range(min(i + m, len(values) - 1), i, -1):
      if j >= len(values) or traps[j]:
        continue

      if values[j] is not None:
        break

      values[j] = i

  if values[-1] is None:
    print(-1)
    return

  index = len(values) - 1
  route = []

  while values[index] != -1:
    route.append(index - values[index])
    index = values[index]

  print(' '.join(str(v) for v in route[::-1]))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M = IL()
s = S()[::-1]

ans = []

now = 0
while True:
  if 0 <= now + M <= N:
    for num in range(1,M+1)[::-1]:
      if s[now + num] == "1":
        continue
      else:
        ans.append(num)
        now += num
        break
    else:
      print(-1)
      exit()
    continue
  else:
    if N - now == 0:
      pass
    else:
      ans.append(N - now)
    break

print(*ans[::-1])

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
s=list(input())
s.reverse()
ans=[]
x=0
while x<n:
  f=0
  for i in range(x+1,min(x+1+m,n+1)):
    if s[i]=='0':
      y=i-x
      f=1
  if f==0:
    print(-1)
    sys.exit()
  ans.append(str(y))
  x+=y
ans.reverse()
print(' '.join(ans))

Submission status: Accepted

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

# 区間更新
# 小さいものを残すパターン
class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.INF = float("inf")
        self.data = [self.INF]*(2*self.n0-1)

    # 0-indexedで[l, r)をvに更新
    # [l, r]を更新したかったら (l, r+1)を引数に入れる
    # minが更新される場合だけ残す
    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                if self.data[r-1] > v:
                    self.data[r-1] = v
            if l&1:
                if self.data[l-1] > v:
                    self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] < res:
                res = self.data[i]
            i = ~-i//2
        return res

n,m = map(int, input().split())
s = input()[:-1]
DP = [-1]*(n+1)
seg = RangeUpdateQuery(n+1)
seg.update(0,1,0)

ss = s[::-1]
for i in range(n):
    if ss[i] == "1":
        continue
    cnt = seg.query(i)
    if cnt == float("inf"):
        continue
    seg.update(i+1, min(i+m+1, n+1), cnt+1)

if seg.query(n) == float("inf"):
    print(-1)
    exit()
a = [seg.query(i) for i in reversed(range(n+1))]
for i in range(n+1):
    if s[i] == "1":
        a[i] = float("inf")

prev = a[0]
j = 0
ans = []
for i in range(n+1):
    if a[i]<prev:
        prev = a[i]
        ans.append(i-j)
        j = i
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    S=list(reversed(list(input())))
    i=0
    f=True
    l=[]
    while True:
        num=0
        for j in range(M):
            if i+(M-j) >= N:
                num=N-i
                break
            else:
                if S[i+(M-j)]=='0':
                    num=M-j
                    break
                else:
                    if j==M-1:
                        f=False
        l.append(str(num))
        i+=num
        if f==False:
            print(-1)
            exit()
        if i >= N:
            break
    print(' '.join(reversed(l)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    s=list(reversed(list(input())))
    cnt=0
    ans=[]
    while cnt<n:
        for i in range(min(m,n-cnt),0,-1):
            if s[cnt+i]=="0":
                cnt+=i
                ans.append(i)
                break
        else:
            print(-1)
            return 0
    print(*list(reversed(ans)))
main()

Submission status: Accepted

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

n = N #現在地
ans = []
while n != 0:
    for i in range(min(n, M), 0, -1):
        if S[n - i] == '0':
            n -= i
            ans.append(i)
            break
        if i == 1:
            print (-1)
            exit()

print (*ans[::-1])

Submission status: Accepted

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

S = [0] * (N+1)
for i in range(N+1):
    if S_raw[i] == '1':
        S[N-i] = 1

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

ans = []
i = 0
while True:
    if i + M >= N:
        ans.append(N - i)
        break
    j = left0[i + M]
    if j == i:
        print(-1)
        exit()
    ans.append(j-i)
    i = j

ans = reversed(ans)
print(*ans)