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:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
S = input()

rS = [i for i in reversed(S)]
res = []
step = 0

lenS = len(S)
while 1:
    if step == lenS-1:
        break
    for i in range(M, -1, -1):
        if step+i > lenS-1:
            continue
        if i == 0:
            print(-1)
            exit()
        if rS[step+i] == '0':
            step += i
            res.append(i)
            break

print(*reversed(res))

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,M = map(int,input().split())
S = input()
 
ans = []
i = N
while i > 0:
    for m in range(M,0,-1):
        if i-m <= 0:
            ans.append(i)
            i = 0
            break
        if S[i-m]=='0':
            ans.append(m)
            i -= m
            break
    else:
        print(-1)
        exit()
print(*ans[::-1])

Submission status: Accepted

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

A = []
c = N
while c > 0:
    d = M
    while d > 0:
        if c - d >= 0 and S[c - d] == "0":
            break
        d -= 1
    else:
        print(-1)
        quit()

    c -= d
    A.append(d)

print(*reversed(A))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from copy import deepcopy
sys.setrecursionlimit(1000000)
s, h = resource.getrlimit(resource.RLIMIT_STACK)
# resource.setrlimit(resource.RLIMIT_STACK, (h, h))
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().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


@mt
def slv(N, M, S):
    def f(s, p):
        if p == 0:
            return s
        elif p < 0:
            return None
        for i in range(M, 0, -1):
            j = p - i
            if j < 0 or j >= len(S):
                continue
            if S[j] == '1':
                continue
            s.append(i)
            v = f(s, j)
            if v:
                return v
            s.pop()
        return None
    
    m = 0
    mm = 0
    for c in S:
        if c == '1':
            mm += 1
            m = max(mm, m)
        else:
            mm = 0
    if m >= M:
        return -1
            
    ans = f([], N)
    if ans:
        return ' '.join(map(str, reversed(ans)))
    return -1
            

        



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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()[::-1]

here = 0
ans = []

while here!=n:
    j = m
    if(here+j>n): j=n-here;
    while s[here+j]!="0":
        j -= 1
        if j<1:
            print(-1)
            exit()
    ans.append(j)
    here += j
print(*ans[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class SWAG(object):
    def __init__(self,dot):
        self.__front=[]; self.__back=[]; self.__dot=dot

    def __bool__(self):
        return bool(self.__front or self.__back)

    def __len__(self):
        return len(self.__front)+len(self.__back)

    def append(self,x):
        back=self.__back
        if(not back): back.append((x,x))
        else: back.append((x,self.__dot(back[-1][1],x)))

    def popleft(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front):
            front.append((back[-1][0],back[-1][0]))
            back.pop()
            while(back):
                front.append((back[-1][0],self.__dot(back[-1][0],front[-1][1])))
                back.pop()
        return front.pop()[0]

    def sum(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front): return back[-1][1]
        elif(not back): return front[-1][1]
        else: return self.__dot(front[-1][1],back[-1][1])

def resolve():
    # input
    n,m=map(int,input().split())
    S=list(map(int,input()))

    # dp
    swag=SWAG(min)
    dp=[None]*(n+1)
    dp[n]=0
    for i in range(n-1,-1,-1):
        swag.append(dp[i+1])
        dp[i]=swag.sum()+1 if(S[i]==0) else INF
        if(len(swag)==m): swag.popleft()

    # output
    if(dp[0]==INF):
        print("-1")
        return
    ans=[]
    now=next=0
    while(now<n):
        next+=1
        if(dp[now]>dp[next]):
            ans.append(next-now)
            now=next
    print(*ans)
resolve()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
n += 1
s = input()
Z = []
for i in range(n):
    if s[i] == "0":
        Z.append(i)
D = [-1] * n
i = len(Z)-1

import sys
for j in range(n-1, -1, -1):
    if s[j] == "0":
        while i >= 0 and j - Z[i] <= m:
            i -= 1
        D[j] = Z[i+1]
        # print(D)
        if j != 0 and j <= Z[i+1]:
            print(-1)
            sys.exit()
# print(D)

a = n-1
ANS = []
while a != 0:
    b = D[a]
    ANS.append(a-b)
    a = b

print(" ".join([str(i) for i in ANS[::-1]]))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
s = input()
q = [(0,N)]
INF = 10**9
dic = {}
for i in range(N-1, -1, -1):
  cnt, j = q[0]
  while j-i>M:
    heappop(q)
    cnt, j = q[0]
  heappush(q, (cnt,j))
  cnt += 1 if s[i]!='1' else INF
  heappush(q, (cnt,i))
  dic[i] = j

if cnt>=INF:
  print(-1)
else:
  x = 0
  while x!=N:
    y = dic[x]
    print(y-x)
    x = y

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()[::-1]

position = 0
steps = []
while position < n:
    position_ = position
    for l in range(m, 0, -1):
        if position+l > len(s)-1:
            continue
        if s[position+l] == '0':
            position += l
            steps.append(l)
            break
    if position == position_:
        steps = [-1]
        break
print(*steps[::-1])

Submission status: Accepted

Solution code:
def f_sugoroku(INF=float('inf')):
    from collections import deque
    N, M = [int(i) for i in input().split()]
    S = input()

    dp = [INF] * (N + 1)  # [v]: 頂点 v からゴール到達までに最低何回かかるか
    dp[N] = 0

    q = deque([0])
    for i in range(N - 1, -1, -1):
        while True:
            if len(q) == 0:
                return '-1'

            if q[0] != INF and len(q) <= M:
                break
            q.popleft()

        if S[i] == '0':
            dp[i] = q[0] + 1
        q.append(dp[i])

    ans = []
    current = 0
    rest = dp[0]  # ゴールまであと何回ルーレットを回すか
    while current < N:
        # dp の値が rest から 1 減るまでインデックスを進める
        i = 1
        rest -= 1  # ルーレットを回した
        while dp[current + i] != rest:
            i += 1

        # ルーレットの出目を答えに追加し、現在位置を進める
        ans.append(i)
        current += i
    return ' '.join(map(str, ans))

print(f_sugoroku())

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    S = f_i.readline().rstrip()
    
    pos = N
    rec = deque()
    while pos:
        for move in range(M, 0, -1):
            next_pos = pos - move
            if next_pos >= 0 and S[next_pos] == '0':
                pos = next_pos
                rec.appendleft(move)
                break
        else:
            print(-1)
            break
    else:
        print(' '.join(str(move) for move in rec))

solve()

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    S = f_i.readline().rstrip()
    
    M *= -1
    pos = N
    rec = deque()
    while pos:
        for move in range(M, 0):
            next_pos = pos + move
            if next_pos >= 0 and S[next_pos] == '0':
                pos = next_pos
                rec.appendleft(move)
                break
        else:
            print(-1)
            break
    else:
        print(' '.join(str(-move) for move in rec))

solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class SWAG(object):
    def __init__(self,dot):
        self.__front=[]
        self.__back=[]
        self.__dot=dot

    def __bool__(self):
        return True if(self.__front or self.__back) else False

    def __len__(self):
        return len(self.__front)+len(self.__back)

    def append(self,x):
        back=self.__back
        if(not back): back.append((x,x))
        else: back.append((x,self.__dot(back[-1][1],x)))

    def popleft(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front):
            front.append((back[-1][0],back[-1][0]))
            back.pop()
            while(back):
                front.append((back[-1][0],self.__dot(back[-1][0],front[-1][1])))
                back.pop()
        front.pop()

    def sum(self):
        assert(self)
        front=self.__front; back=self.__back
        if(not front): return back[-1][1]
        elif(not back): return front[-1][1]
        else: return self.__dot(front[-1][1],back[-1][1])

def resolve():
    n,m=map(int,input().split())
    S=list(map(int,input()))
    swag=SWAG(min)
    dp=[INF]*(n+1)
    dp[n]=0
    for i in range(n-1,-1,-1):
        if(i+1+m<=n): swag.popleft()
        swag.append(dp[i+1])
        if(S[i]==1): continue
        dp[i]=swag.sum()+1

    if(dp[0]==INF):
        print(-1)
        return

    ans=[]
    now=0
    next=0
    while(now!=n):
        next+=1
        if(dp[next]!=INF and dp[now]!=dp[next]):
            ans.append(next-now)
            now=next
    print(*ans)
resolve()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
s=deque(input())
a=0
for i in range(n+1):
  if s[i]=="1":
    a=a+1
    if a==m:
      print(-1)
      break
  else:
    a=0
if a==0:
  b=deque([])
  d=n
  while d>0:
    if d<=m:
      b.appendleft(d)
      d=0
    else:
      i=m
      while i>0:
        if s[d-i]=="1":
          i=i-1
        else:
          b.appendleft(i)
          d=d-i
          for j in range(i):
            s.pop()
          break
  for i in range(len(b)):
    print(b[i],end=" ")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=list(input())
s.reverse()
now=0;l=[]
while True:
  tmp=now
  now+=m
  now=min(n,now)
  if now==n:
    l.append(str(now-tmp))
    break
  while s[now]=='1':
    now-=1
    if now==tmp:
      print(-1)
      exit()
  l.append(str(now-tmp))
l.reverse()
print(' '.join(l))

Submission status: Accepted

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

import sys
while P<N:
    k=0
    for i in range(1,M+1):
        if P+i>N:
            break
        if S[P+i]=='0':
            k=i
    if k==0:
        print(-1)
        sys.exit()
    L.append(k)
    P+=k

L=L[::-1]
print(*L)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [0] * (n+1)
cnt = 0
for i, x in enumerate(input()):
    if x == "1":
        cnt += 1
        if cnt >= m: print(-1); exit()
        s[i] = 1
    else: cnt = 0

c = n
res = []

while True:
    nc = c - m
    if nc <= 0:
        res.append(c)
        break
    while s[nc]: nc += 1
    res.append(c - nc)
    c = nc

print(*reversed(res))

Submission status: Accepted

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

# dp[i] := ゴールから最短何手でマスiにたどり着けるか
dp = [float('inf')] * (N + 1)
dp[-1] = 0


class RangeMinimumQuery:
    def __init__(self, n, inf=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INF = inf
        self.segtree = [self.INF] * (2 * self.n)

    # i番目の値(0-indexed)をxに変更
    def update(self, i, x):
        i += self.n
        self.segtree[i] = x
        while i > 0:
            i //= 2
            self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

    # [l, r)のmin
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        R = min(R, len(self.segtree))
        s = self.INF
        while L < R:
            if L & 1:
                s = min(s, self.segtree[L])
                L += 1

            if R & 1:
                s = min(s, self.segtree[R - 1])
                R -= 1

            L >>= 1
            R >>= 1

        return s


# セグメント木でdpテーブルを高速に埋める
RMQ = RangeMinimumQuery(N + 1)
RMQ.update(N, 0)
for i in range(N - 1, -1, -1):
    if S[i] == '1':
        continue

    # RMQ.query(l, r) := [l, r)の最小値
    dp[i] = RMQ.query(i, i + M + 1) + 1
    RMQ.update(i, dp[i])


ans = []
position = 0
while position < N:
    for move in range(1, M + 1):
        if position + move > N:
            continue

        if S[position + move] == '1':
            continue

        # 最短手数にならない
        if dp[position + move] == dp[position]:
            continue

        ans.append(move)
        position += move
        break

    else:
        print(-1)
        exit()

print(*ans)

Submission status: Accepted

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


# 後ろから貪欲
ans = []
position = N
while position > 0:
    for move in range(M, 0, -1):
        if position - move < 0:
            continue

        if S[position - move] == '1':
            continue

        ans.append(move)
        position -= move
        break
    else:
        print(-1)
        exit()

print(*ans[::-1])

Submission status: Accepted

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

x = N
while x:
    for i in range(max(x-M, 0), x):
        if S[i] == "0":
            ANS.append(x-i)
            x = i
            break
    else:
        print(-1)
        break
else:
    print(*ANS[::-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S,r,s=input(),[],N
for _ in range(2*N):
    if S[s]=='1':
        s+=1
    else:
        if N-s:
            r.append(N-s)
        N,s=s,max(0,s-M)
print(*[-1] if s else r[::-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S,r,s=input(),[],N
for _ in range(2*N):
    if S[s]=='1':
        s += 1
    else:
        r.append(str(N-s))
        N,s=s,max(0,s-M)
    if N == 0:
        break
print(*[-1] if s else r[1:][::-1])

Submission status: Accepted

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

ans=[]
ind=N
while ind>0:
  j=0
  for i in range(max(ind-M,0),ind):
    if S[i]==0:
      ans.append(ind-i)
      ind=i
      j=1
      break
  if j==0:
    print(-1)
    exit()
      
print(*reversed(ans))

Submission status: Accepted

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


class SegmentTree1():
    """
    1-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, operation_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n)  # binary tree
        self.ele_id = ele_id  # identity element
        self.operation_func = operation_func  # binary operation of monoid

    def __getitem__(self, idx):
        return self.data[idx + self.n]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n] = data_init[i]
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.operation_func(self.data[2 * i],
                                               self.data[2 * i + 1])

    def update(self, idx, x):
        # change idx-th element to x (idx : 0-indexed)
        idx += self.n
        self.data[idx] = x
        while idx > 1:
            idx = idx >> 1
            self.data[idx] = self.operation_func(self.data[2 * idx],
                                                 self.data[2 * idx + 1])

    def query(self, l, r):
        # query for interval [l, r) (l, r : 0-indexed)
        l += self.n
        r += self.n
        ret = self.ele_id
        while l < r:
            if l & 1:  # right child
                ret = self.operation_func(ret, self.data[l])
                l += 1
            if r & 1:  # right child
                r -= 1
                ret = self.operation_func(ret, self.data[r])
            # go to parent-nodes
            l = l >> 1
            r = r >> 1
        return ret


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

dp = [-1] * (n + 1)
dp[n] = 1
roulette = [0] * (n + 1)

INF = 10**10
INF_PAIR = (INF, -1)
operation_func = lambda a, b: a if a[0] < b[0] else (b if a[0] > b[0] else
                                                     (a if a[1] < b[1] else b))
rmq = SegmentTree1(n + 1, INF_PAIR, operation_func)
rmq.update(n, (0, n))
for i in range(n - 1, -1, -1):
    if s[i] == '1':
        continue
    val, idx = rmq.query(i + 1, min(n, i + m) + 1)
    if val != INF:
        roulette[i] = idx - i
        dp[i] = val + 1
        rmq.update(i, (val + 1, i))

if dp[0] == -1:
    print(-1)
else:
    ans = []
    idx = 0
    while idx < n:
        ans.append(roulette[idx])
        idx += roulette[idx]
    print(*ans)

Submission status: Accepted

Solution code:
import sys
n, m = map(int, input().split())
s = input()[::-1]
ans = []
tmp = 0
while tmp < n:
	for i in range(min(m, n-tmp), 0, -1):
		if s[tmp+i] == "0":
			tmp += i
			ans.append(str(i))
			break
	else:
		print(-1)
		sys.exit()
print(" ".join(ans[::-1]))

Submission status: Accepted

Solution code:
n,m=[int(j) for j in input().split()]
s=input()[::-1]
l=[]
for i in range(n+1):
    if s[i]=="0":
        l.append(i)
import bisect
ans=[]
c=0
while True:
    if c+m>=n:
        ans.append(n-c)
        break
    p=bisect.bisect_right(l,c+m)-1
    ans.append(l[p]-c)
    if l[p]-c==0:
        print(-1)
        exit()
    c=l[p]
    if c==n:
        break
print(*ans[::-1])

Submission status: Accepted

Solution code:
# F - Sugoroku
N, M = map(int, input().split())
S = str(input())

disable = False
answer = []
i = N
while i > 0:
    if i <= M:
        answer.append(i)
        break
        
    move = M
    while S[i - move] == "1":
        move -= 1

    if move == 0:
        disable = True
        break
        
    answer.append(move)
    i -= move
    
if disable:
    print(-1)
else:
    L = len(answer)
    for j in range(L):
        print(answer[L - j - 1], end=" ")

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,m = m()

a = list(map(int,input()))

on = cl.deque()
la = n

while True:
    if la == 0:
        break
    for i in range(m,0,-1):
        if la - i >= 0 and a[la-i] == 0:
            la -= i
            on.appendleft(i)
            break
    else:
        print(-1)
        exit()
print(jo(on))

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()

answer = [] # 後ろからできるだけ遠くに行く
S = S[::-1]
cur = 0
while cur < N:
    for i in range(M, 0, -1):
        if cur+i <= N and S[cur+i] == '0':
            answer.append(i)
            cur += i
            break
    else:
        print(-1)
        exit()
print(*answer[::-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
ans=[]
now=n
while now>0:
    for i in range(m,0,-1):
        if now-i<0:
            continue
        if s[now-i]=='0':
            ans.append(str(i))
            now-=i
            break
    else:
        print(-1)
        exit()
print(' '.join(ans[::-1]))

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()

## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n,0)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:

    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2]) 
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res

    def __str__(self):
        # 生配列を表示
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

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

def dp(b,m): # N log (N)
    N=len(b)-1
    n=N+1
    sg=SegTree(n,inf,min,inf)

    sg.update(0,0)

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

    return dp

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

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

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

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=input()
ans=[]
w=n
while w:
    x=0
    for i in range(1,m+1):
        if w-i>=0 and s[w-i]=='0':
            x=i
    if x==0:
        print(-1)
        exit()
    else:
        ans.append(x)
        w-=x
print(*ans[::-1])

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()

## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n,0)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:
    seg=[]
    num=0  # num:n以上の最小の2のべき乗
    ide_ele=0  # 単位元
    def segfun():
        return

    def __init__(self,n,init_val,segfun=sum,ide=0):
        self.ide_ele=ide
        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
        self.segfun=segfun
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=segfun(self.seg[2*i+1],self.seg[2*i+2]) 
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


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
    sg=SegTree(n,inf,min,inf)

    sg.update(0,0)

    dp=[0]+[inf]*(N)
    for i in range(N):
        if b[i+1]==1:
            continue
        dp[i+1]=sg.query(max(i-m+1,0),i+1)+1
        sg.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
    move.append(j)

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

Submission status: Accepted

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

position = 0
count = 0
answer = []
while True:
    for i in range(M, -1, -1):
        if i == 0:
            print(-1)
            sys.exit()
        if position + i > N:
            continue
        if S[position + i] == '0':
            answer.append(i)
            position += i
            break
    if position >= N:
        break
for i in reversed(answer):
    print(i)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())
s = input()
INF = 10**18
dp_cnt = [INF]*(N+1)
dp_next = [0]*(N+1)
dp_cnt[N] = 0
q = [(0,N)]

for i in range(N-1, -1, -1):
  while True:
    cnt, j = q[0]
    if j-i>M:
      heappop(q)
    else:
      break
  dp_cnt[i] = cnt
  if s[i]=='1':
    cnt = INF
    j = 0
  cnt += 1
  heappush(q, (cnt, i))
  dp_next[i] = j

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

x = 0
ans = []
while x<N:
  y = dp_next[x]
  ans += [str(y-x)]
  x = y

print(*ans)

Submission status: Accepted

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

l = []
i = 0
while i < N:
  t = T[i+1: i+M+1][::-1]
  if '0' not in t:
    print(-1)
    exit()
  else:
    x = min(M - t.index('0'), len(t))
    l.append(x)
    i += x
print(*l[::-1])