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:
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:
from bisect import bisect_left, bisect_right

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

OKs = []
for i, S in enumerate(Ss):
    if S == '0':
        OKs.append(i)
#print('OKs:', OKs)

dp = [0] * (N+1)
for i in range(N+1):
    j = bisect_left(OKs, i-M)
    dp[i] = OKs[j]
#print('dp:', dp)

anss = []
i = N
while True:
    iPrev = dp[i]
    if iPrev == i:
        anss = []
        break
    if iPrev < 0:
        iPrev = 0
    anss.append(i-iPrev)
    if iPrev == 0:
        break
    i = iPrev

if not anss:
    print(-1)
else:
    print(' '.join(map(str, anss[::-1])))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


INF = -float('inf')
N, M = map(int, input().split())
S = input()[:-1]
Seg = SegmentTree(N+1, lambda a, b: max(a, b), INF)
for i, c in enumerate(reversed(S)):
    if c == "0":
        Seg.set(i, i)
Seg.build()
ans = []
cur = 0

while True:
    nex = Seg.query(min(cur+1, N), min(cur+M+1, N+1))
    if nex == INF:
        ans = [-1]
        break
    else:
        ans.append(nex-cur)
        cur = nex
        if cur == N:
            break
print(" ".join(map(str, reversed(ans))))

Submission status: Accepted

Solution code:
from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq
dq = deque()
N,M = map(int, input().split())
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [-1 for _ in range(N+1)]
dq.append(0)
for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    idx = dq[0]
    if c != "1" and dp1[idx] != INF:
        dp1[i] = dp1[idx] + 1
        dp2[i] = idx
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    r = []
    s = N
    while True:
        if s == 0:
            break
        ns = dp2[s]
        r.append(s-ns)
        s = ns
    print(" ".join(map(str, r[::-1])))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

n,m=map(int,input().split())
s=input()
if m>n:
    m=n
tmp=-1
for i in range(m):
    if s[-i-2]=="0":
        tmp=-i-2
# print(tmp)
li=[]
for i in range(n):
    li.append(tmp)
    a=-i-2-m
    if a<-1-n:
        a=-1-n
    if s[a]=="0":
        tmp=a
ans=[]
i=-1
li.reverse()

while(i!=-n-1):

    if li[i]==i:
        print(-1)
        quit()
    ans.append(i-li[i])
    i=li[i]

ans.reverse()


for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,m=MI()
    s=input()[::-1]
    now=0
    ans=[]
    while now<n:
        for d in range(m,0,-1):
            if now+d>n:continue
            if s[now+d]=="0":
                now+=d
                ans.append(d)
                break
        else:
            print(-1)
            exit()
    print(*ans[::-1])

main()

Submission status: Accepted

Solution code:

n, m = [int(s) for s in input().split()]
s = [int(s) for s in input()]
board = [None]*(n+1)
left = 0
board[left] = 0
for i in range(1,n+1):
    if s[i]:
        continue
    left = max(left, i-m)
    while board[left] is None:
        left += 1
        if left == i:
            break
    if left < i:
        board[i] = left
# print(board)
if board[n] is None:
    print(-1)
else:
    steps = []
    j = n
    while True:
        step = j - board[j]
        steps.append(step)
        j = board[j]
        if j==0:
            break
    print(' '.join(str(s) for s in steps[::-1]))

Submission status: Accepted

Solution code:
from bisect import bisect_right
N, M = map(int, input().split())
S = input()

A = [i for i, s in enumerate(S) if s == '0']
now = N
ans = []

while True:
    left = bisect_right(A, now - M - 1)
    new = A[left]
    ans.append(now - new)
    if new == 0:
        break
    if new == now:
        print(-1)
        exit()
    now = new

print(*ans[:: -1])

Submission status: Accepted

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

if S.find('1'*M) >= 0:
    print(-1)
    exit()

ans = []
i = 0
while i < N:
    a = S[i:i+M+1].rfind('0')
    ans.append(a)
    i += a

print(*ans[::-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
S=[]
for i,ss in enumerate(s):
  if ss=="0":
    S.append(i)
Ans=[]
cur=n
chk=True
import bisect
while cur>0:
  next=S[bisect.bisect_left(S,max(0,cur-m))]
  if next==cur:
    chk=False
    break
  else:
    Ans.append(cur-next)
    cur=next
if not chk:
  print(-1)
else:
  Ans=Ans[::-1]
  print(*Ans)

Submission status: Accepted

Solution code:
def main():
    N, M  = [int(i) for i in input().split()]
    S  = [int(i) for i in input()]
    loc = N
    a = []
    while loc:
        for i in range(min(loc, M), 0, -1):
            if S[loc - i] == 1:
                continue
            a.append(i)
            loc -= i
            break
        else:
            return '-1'
    return ' '.join(str(i) for i in reversed(a))


print(main())

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":
      x-=i
      a.append(i)
      break
    if i==1:print(-1);exit()
print(*a[::-1])

Submission status: Accepted

Solution code:
import sys

def solve():
    N, M = map(int, input().split())
    S = input()
    Ans_rev = []
    current_id = N
    while True:
        length = 0
        for i in range(M):
            if current_id - i - 1 >= 0:
                if S[current_id - i - 1] == "0":
                    length = i + 1
            else: break
        if length > 0: 
            Ans_rev.append(length)
            current_id -= length
        else:
            break
    if current_id > 0: print(-1)
    else:
        Ans = []
        for i in reversed(range(len(Ans_rev))):
            Ans.append(Ans_rev[i])
        print(" ".join(map(str, Ans)))
            

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

# dp[i]=iに行くのに最短の手数
dp=[0]*(n+1)
ans=0
now=n
count=0
flag=True
ans=[]
for i in range(10**11):
    if flag==False:
        break
    for j in range(m,0,-1):
        if now-j<=0:
            ans.append(now)
            flag=False
            break
        elif s[now-j]!='1':
            ans.append(j)
            count+=1
            now-=j
            break
        else:
            if j==1:
                print(-1)
                exit()
            continue
        

ans.reverse()

print(*ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = input()
ret = []
i = n
while i > 0:
    best = max(i - m, 0)
    if a[best] == '1':
        while best < i and a[best] == '1':
            best += 1
        if best == i:
            print(-1)
            exit()
    ret.append(i - best)
    i = best
print(' '.join(map(str, ret[::-1])))

Submission status: Accepted

Solution code:
class SegTreeIndex(object):
    # 区間の最小 or 最大値とその index を取得
    # 検証: https://yukicoder.me/submissions/376308
    __slots__ = ["elem_size", "tree", "default", "op", "index", "op2"]
    def __init__(self, a: list, default=float("inf"), op=lambda a,b: b if a>b else a, op2=lambda a,b:a>b):
        # 同じ場合最左のインデックスを返す
        # 最小値・最左: default=float("inf"), op=lambda a,b: b if a>b else a, op2=lambda a,b:a>b
        # 最大値・最左: -float("inf"), max, lambda a,b:a<=b
        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)
        self.index = index = [0] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        index[elem_size:elem_size + real_size] = list(range(real_size))
        self.default = default
        self.op = op
        self.op2 = op2
        for i in range(elem_size-1, 0, -1):
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]

    def get_value(self, x: int, y: int) -> tuple:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, op, op2, index = self.tree, self.op, self.op2, self.index
        result_l = result_r = self.default
        idx_l = idx_r = -1
        while l < r:
            if l & 1:
                v1, v2 = result_l, tree[l]
                result_l = op(v1, v2)
                if op2(v1, v2)==1:
                    idx_l = index[l]
                l += 1
            if r & 1:
                r -= 1
                v1, v2 = tree[r], result_r
                result_r = op(v1, v2)
                if op2(v1, v2)==0:
                    idx_r = index[r]
            l, r = l >> 1, r >> 1
        result = op(result_l, result_r)
        idx = idx_r if op2(result_l, result_r) else idx_l
        return result, idx

    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, index, op2 = self.op, self.tree, self.index, self.op2
        while i > 1:
            i >>= 1
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]

def main():
    N, M = map(int, input().split())
    S = list(map(int, input()))
    dp = [10 ** 9] * (N + 1)
    seg = SegTreeIndex(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_value(max(i - M, 0), i)
        if v == 1000000000:
            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)))


main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

N, M = map(int, input().split())
S = input()
out = []
for i, x in enumerate(S):
    if x == '1':
        out.append(N - i)
#print('out={}'.format(out))

p = 0
ans = []
while p < N:
    d = min(M, N - p)
    #print('start with d={}'.format(d))
    while p + d in out and d >= 1:
        d -= 1
    if d == 0:
        print(-1)
        exit()
    ans.append(d)
    p += d
if p == N:
    ans.reverse()
    print(' '.join(map(str, ans)))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_right

N,M = II()
A = str(input())

B = A[::-1]

ans = []
place = 0
while place!=N:
    for i in range(1,M+1)[::-1]:
        if place+i<=N:
            if B[place+i]!='1':
                ans.append(i)
                place += i
                break
        if i==1 and B[place+i]=='1':
            print(-1)
            exit()

print(*list(reversed(ans)))

Submission status: Accepted

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

i=n
ans=[]
while i>0:
    if i<=m:
        ans.append(i)
        break
    j=m
    while True:
        if j==0:
            print(-1)
            exit()
        if s[i-j]:
            j-=1
        else:
            ans.append(j)
            i-=j
            break


ans.reverse()
print(*ans)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()
S = read()[:-1]
S = S[::-1]
ans = []
cur_i = 0
while True:
    dice = M
    cur_i += dice
    if cur_i > N:
        if N - (cur_i - M) == 0:
            pass
        else:
            ans.append(N - (cur_i - M))
        break
    # if cur_i == N + 1:
    #     ans.append(cur_i - N)
    #     break
    while S[cur_i] == '1':
        cur_i -= 1
        dice -= 1
        if dice == 0:
            print(-1)
            exit()
    ans.append(dice)
print(*ans[::-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
s = s[::-1]
idx = 0
ans = []
while(True):
    d = s[idx + 1:idx + m + 1].rfind('0')
    if d == -1:
        print(-1)
        break
    ans.append(d + 1)
    idx += d + 1
    if idx == n:
        print(*ans[::-1])
        break

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class SegTreeIndex(object):
    # 区間の最小 or 最大値とその index を取得
    # 検証: https://yukicoder.me/submissions/376308
    __slots__ = ["elem_size", "tree", "default", "op", "index", "op2"]
    def __init__(self, a: list, default=float("inf"), op=lambda a,b: b if a>b else a, op2=lambda a,b:a>b):
        # 同じ場合最左のインデックスを返す
        # 最大値・最左 -> -float("inf"), max, lambda a,b:a<=b
        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)
        self.index = index = [0] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        index[elem_size:elem_size + real_size] = list(range(real_size))
        self.default = default
        self.op = op
        self.op2 = op2
        for i in range(elem_size-1, 0, -1):
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]

    def get_value(self, x: int, y: int) -> tuple:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, op, op2, index = self.tree, self.op, self.op2, self.index
        result_l = result_r = self.default
        idx_l = idx_r = -1
        while l < r:
            if l & 1:
                v1, v2 = result_l, tree[l]
                result_l = op(v1, v2)
                if op2(v1, v2)==1:
                    idx_l = index[l]
                l += 1
            if r & 1:
                r -= 1
                v1, v2 = tree[r], result_r
                result_r = op(v1, v2)
                if op2(v1, v2)==0:
                    idx_r = index[r]
            l, r = l >> 1, r >> 1
        result = op(result_l, result_r)
        idx = idx_r if op2(result_l, result_r) else idx_l
        return result, idx

    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, index, op2 = self.op, self.tree, self.index, self.op2
        while i > 1:
            i >>= 1
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]


N, M = map(int, input().split())
S = list(map(int, input()))
dp = [10 ** 9] * (N + 1)
seg = SegTreeIndex(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_value(max(i - M, 0), i)
    if v == 1000000000:
        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:
inf = float('inf')

# 一点更新　区間取得　1-indexed
class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        # self.N : 完全二分木の葉の数(N以上の最小の2べき)
        self.N = tmp
        # 2*self.N - 1 : 完全二分木のノード数
        # 1-indexedで管理するので１つ余分に設ける
        self.Data = [(inf, -1) for _ in range(2*self.N)]

    # k (0-indexed)
    def update(self, k, x):
        #　インデックスを補正
        k += self.N
        # 指定ノードを更新
        self.Data[k] = (x, k-self.N)
        # kを含む区間ノードを更新していく
        while k > 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    # [l, r) (0-indexed)
    def query(self, l, r):
        #　インデックスを補正
        l += self.N
        r += self.N
        # 返り値を初期化
        res = (inf, -1)
        while l < r:
            # 右側なら右側を更新 右上に行く
            # 左側なら更新しない　上に行く
            if l & 1:
                res = min([res, self. Data[l]])
                l += 1
            # 右側なら左側を更新　上に行く
            # 左側なら更新しない 上に行く
            if r & 1:
                r -= 1
                res = min([res, self.Data[r]])
            l >>= 1; r >>= 1
        return res

    def value(self, k):
        k += self.N
        return self.Data[k]

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

ST = SegmentTree(N+1)
ST.update(0, 0)
memo = [-1] * (N+1)

for i in range(1, N+1):
    l = max(i-M, 0)
    r = i
    if S[i] == "0":
        d, j = ST.query(l, r)
        if d != inf:
            ST.update(i, d+1)
            memo[i] = j

if ST.value(N)[0] == inf:
    print(-1)
    exit()

ans = []
now = N
while now != 0:
    pre = memo[now]
    ans.append(now-pre)
    now = pre

print(*ans[::-1])

Submission status: Accepted

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

inf = float('inf')

# 一点更新　区間取得　1-indexed
class SegmentTree:
    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp <<= 1
        # self.N : 完全二分木の葉の数(N以上の最小の2べき)
        self.N = tmp
        # 2*self.N - 1 : 完全二分木のノード数
        # 1-indexedで管理するので１つ余分に設ける
        self.Data = [(inf, -1) for _ in range(2*self.N)]

    # k (0-indexed)
    def update(self, k, x):
        #　インデックスを補正
        k += self.N
        # 指定ノードを更新
        self.Data[k] = (x, k-self.N)
        # kを含む区間ノードを更新していく
        while k > 1:
            k >>= 1
            self.Data[k] = min([self.Data[2*k], self.Data[2*k+1]])

    # [l, r) (0-indexed)
    def query(self, l, r):
        #　インデックスを補正
        l += self.N
        r += self.N
        # 返り値を初期化
        res = (inf, -1)
        while l < r:
            # 右側なら右側を更新 右上に行く
            # 左側なら更新しない　上に行く
            if l & 1:
                res = min([res, self. Data[l]])
                l += 1
            # 右側なら左側を更新　上に行く
            # 左側なら更新しない 上に行く
            if r & 1:
                r -= 1
                res = min([res, self.Data[r]])
            l >>= 1; r >>= 1
        return res

    def value(self, k):
        k += self.N
        return self.Data[k]

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

ST = SegmentTree(N+1)
ST.update(0, 0)
memo = [-1] * (N+1)

for i in range(1, N+1):
    l = max(i-M, 0)
    r = i
    if S[i] == "0":
        d, j = ST.query(l, r)
        if d != inf:
            ST.update(i, d+1)
            memo[i] = j

if ST.value(N)[0] == inf:
    print(-1)
    exit()

ans = []
now = N
while now != 0:
    pre = memo[now]
    ans.append(now-pre)
    now = pre

print(*ans[::-1])

Submission status: Accepted

Solution code:

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

S.reverse()
ans = []

i = 0
while(True):
    for j in range(M, 0, -1):
        if i + j >= N:
            ans.append(N - i)
            i = N
            break
        if S[i + j] == "0":
            ans.append(j)
            i += j
            break
    else:
        print(-1)
        exit(0)
    if i == N:
        break

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

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()

# 後ろから貪欲
ans = []
S = S[::-1]

pos = [N + 1] * len(S)
p = N + 1
l = N
while p - l <= M and l >= 0:
    pos[l] = p
    l -= 1
p -= 1
while p >= 0:
    if S[p] == '1':
        p -= 1
        continue

    while p - l <= M and l >= 0:
        pos[l] = p
        l -= 1
    p -= 1

i = 0
while i < N:
    me = None
    for j in reversed(range(1, min(M + 1, pos[i] - i + 1))):
        if i + j < len(S) and S[i + j] == '0':
            me = j
            break
    if me is None:
        print(-1)
        exit()
    ans.append(me)
    i += me
print(*ans[::-1])

Submission status: Accepted

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

max_len = 0
for i in range(N + 1):
    if S[i] == '0':
        current_len = 0
    else:
        current_len += 1
        max_len = max(current_len, max_len)

if max_len >= M:
    ans = -1
else:
    order = []
    i = N
    while i > 0:
        c = min(M, i)
        while S[i - c] == '1':
            c -= 1
        order.append(str(c))
        i -= c
    ans = ' '.join(order[::-1])

print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def rle(s):
    import itertools
    return list(map(lambda x: (x[0], len(list(x[1]))), itertools.groupby(s)))


n, m = ril()
s = rs()
ls = rle(s)

for a, b in ls:
    if a == '1' and b >= m:
        print(-1)
        exit()

acc = [ls[-1][1]]
for a, b in reversed(ls[:-1]):
    acc.append(acc[-1] + b)

res = []
pos = 0

while True:
    if pos == n:
        break
    i = bisect.bisect(acc, pos + m)
    if i % 2 == 0:
        if pos + m < n + 1:
            res.append(m)
            pos += m
        else:
            res.append(n - pos)
            break
    else:
        new_pos = acc[i - 1] - 1
        res.append(new_pos - pos)
        pos = new_pos
print(*res[::-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
input = sys.stdin.readline
INF = 10**9

n, m = [int(item) for item in input().split()]
s = input().rstrip()
s = s[::-1]
frm = 0
ans = []
ok = True
while frm < n:
    nxt = s[frm:frm+m+1].rfind("0")
    if nxt == 0:
        ok = False
        break
    ans.append(nxt)
    frm += nxt
if not ok:
    print(-1)
else:
    print(" ".join([str(item) for item in ans[::-1]]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = input()
a = []
c = n
while True:
  if c <= m:
    a.append(c)
    break
  for i in range(m,0,-1):
    if s[c-i] =='0':
      a.append(i)
      c -= i
      break
    if i == 1:
      print(-1)
      exit()
print(*a[::-1],sep=' ')

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

reach = []
for i, s in enumerate(S) :
    if s == '0' :
        reach.append(i)

def solve() :
    ret = []
    cur = N
    while cur != 0 :
        i = bisect_left(reach, cur - M)
        if reach[i] == cur :
            return [-1]
        ret.append(cur - reach[i])
        cur = reach[i]
    
    ret.reverse()
    return ret
    
print(*solve())

Submission status: Accepted

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

i=n
ans=[]
while i>0:
    if i<=m:
        ans.append(i)
        break
    j=m
    while True:
        if j==0:
            print(-1)
            exit()
        if s[i-j]:
            j-=1
        else:
            ans.append(j)
            i-=j
            break


ans.reverse()
print(*ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
ans=[]
p=n
while p>0:
	flag=False
	k=min(p,m)
	for i in range(min(m,p)):
		if s[p+i-k]=="0":
			flag=True
			ans.append(k-i)
			p=p+i-k
			break
	if flag==False:
		print(-1)
		exit()
print(*ans[::-1])

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n, m = map(int, input().split())
    s = list(input())[::-1]

    now = 0
    ansl = []
    while now != n:
        tm = min(n - now, m)
        pnow = now
        while tm > 0 and now+tm < len(s):
            if s[now + tm] == "0":
                now += tm
                ansl.append(tm)
                break
            else:
                tm -= 1
        
        if pnow == now:
            print(-1)
            exit()
        

    ansl = ansl[::-1]
    for i in range(len(ansl)):
        if ansl[i] == 0:
            continue
        print(*ansl[i:])
        exit()
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
n,m = map(int,input().split( ))
s = input()
l= len(s)
s_id = []
sm = 0
for i in range(l):
    if not int(s[i]):
        s_id.append(i)

ans = []
now = n
while now>0:
    #print(now)
    nxt = now-m
    j = bisect_left(s_id,nxt)
    if s_id[j] <now-m:
        j+=1
    if s_id[j]==now:
        print(-1)
        exit()
    ans.append(now-s_id[j])
    now = s_id[j]
ans.reverse()
print(*ans)