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:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, S: str):
    # dp = [float('inf')]*(N+1)
    # dp[N] = 0
    # count = 1
    # for i in range(N,-1,-1):
    #     if S[i] == "1":
    #         continue
            
    #     for j in range()
    S = S[::-1]
    cur_index = 0
    answer = []
    while True:
        for i in range(M,0,-1):
            if cur_index+i >= N:
                answer.append(N-cur_index)
                answer.reverse()
                print(*answer)
                return

            if S[cur_index+i] == "1":
                continue
            else:
                cur_index += i
                answer.append(i)
                break
        else:
            print(-1)
            return
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)
    solve(N, M, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# print("%d,%d" % (N, M))
# print(S)
if S[0] == 1 or S[-1] == 1:
    print(-1) # no route
    exit(0)

pos = len(S) - 1
move = []
while pos >= 0:
    if pos - M <= 0:
        move.append(pos)
        break
    
    found = False
    for idx in range(pos - M, pos):
        if S[idx] == '0':
            found = True
            break
    
    if not found:
        move = None
        break # no route
    
    move.append(pos - idx)
    pos = idx

if move is None:
    print(-1)
else:
    move.reverse()
    print(' '.join(list(map(str, move))))

Submission status: Accepted

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

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'))
    res = []
    start = n
    while True:
        b = False
        for j in range(max(0, start - m), start):
            if s[j] == "0":
                res.append(start - j)
                start = j
                b = True
                break
        if not b:
            print(-1)
            exit()
        else:
            if j == 0:
                res.reverse()
                print(*res)
                exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N, M = ints()
N+=1
G=N-1
SUGOROKU = input()

if SUGOROKU[G]==1:
  print(-1)
  exit()

n = N-1
k = 0
tejun = []
while n>0:
  mmax = min(n, M)

  found = False
  for m in reversed(range(1, mmax+1)):
    if SUGOROKU[n-m]=='1':
      continue
    n -= m
    k += 1
    found = True
    tejun.append(m)
    break

  if not found:
    print(-1)
    exit()

print(*list(reversed(tejun)))

Submission status: Accepted

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

if "1"*m in s:
  print(-1)
  exit(0)

ans=[]
cur=0
while cur<len(s):
  for j in range(m,0,-1):
    if cur+j>=len(s):
      continue
    if s[cur+j]=="0":
      cur=cur+j
      ans.append(j)
      break
  if cur==len(s)-1:
    break

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

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = input().strip()
seq = [n]
p = n
while p>0:
    ddprint("p {}".format(p))
    p0 = p
    for i in range(max(0,p-m),p):
        if s[i]=='0':
            ddprint("add {}".format(i))
            seq.append(i)
            p = i
            break
    if p==p0:
        print(-1)
        exit()
seq.reverse()
for i in range(len(seq)-1):
    printn(str(seq[i+1]-seq[i])+' ')
print('')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc146/submissions/8617148

def solve(N, M, S):
    from collections import namedtuple
    from heapq import heappop, heappush

    INF = N * 2
    V = namedtuple('V', 'cnt index')

    cnt_from_N = [INF] * (N + 1)
    cnt_from_N[N] = 0

    parent = [0] * (N + 1)

    h = [V(cnt=0, index=N)]

    for j in range(N - 1, -1, -1):
        # S[j]に到達する最小回数とその経路を求める
        if S[j]:
            continue

        while h:
            cnt, par = h[0]
            if par > j + M:
                # jまで移動できない(距離>M)
                heappop(h)
                continue
            break
            # jまで最小回数で到達できる頂点par
            # parまでの回数cnt

        if not h:
            return -1,
            # jまで到達できる頂点がない

        cnt_from_N[j] = cnt + 1
        parent[j] = par

        heappush(h, V(cnt=cnt + 1, index=j))

    ret = []
    curr = 0
    while curr < N:
        par = parent[curr]
        ret.append(par - curr)
        curr = par

    return ret


def main():
    N, M = map(int, input().split())
    *S, = map(int, input())
    print(*solve(N, M, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = "x" + input()[::-1]
#print("S:", S)

current = 1
masu = [1]

while 1:
  flag = 1
  for i in range(min(current + M, N + 1), current, -1):
    if S[i] == "0":
      flag = 0
      masu.append(i)
      current = i
      break
  if flag:
    print(-1)
    exit()
  if current == N + 1:
    masu = masu[::-1]
    #print("masu:", masu)
    answer = []
    for i in range(1, len(masu)):
      answer.append(- masu[i] + masu[i - 1])
    print(*answer)
    exit()

Submission status: Accepted

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

# process
ans = [0]

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

    if ans[0] == -1:
        break

# output
if ans[0] == -1:
    print("-1")
else:
    ans.pop(0)
    print(" ".join(map(str, (ans[::-1]))))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200001)

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

p1 = False
x1 = 0
m1 = N
c1 = 0
for n in S:
    if n == "1":
        if p1:
            c1 += 1
        else:
            c1 = 1
            p1 = True
    else:
        p1 = False
        if c1 > 0:
            if c1 > x1:
                x1 = c1
            if c1 < m1:
                m1 = c1
           
def rest(l, ans):
    s = M
    while s > 0:
        if s >= l:
            ans.append(l)
            return ans
        if S[l-s] == "1":
            if s == 1:
                return -1
            s -= 1
            continue
        l -= s
        if rest(l, ans) == -1:
            s -= 1
        else:
            ans.append(s)
            return ans
    return -1

if x1 > M - 1:
    ans = -1
else:
    ans = rest(N, [])

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

Submission status: Accepted

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

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():
    n,m=map(int,input().split())
    S=list(map(int,input()))
    dp=[INF]*(n+1) # dp[i] : i から何手でゴールできるか
    dp[-1]=0

    swag=SWAG(min)
    for i in range(n-1,-1,-1):
        swag.append(dp[i+1])
        if(len(swag)>m): swag.popleft()
        if(S[i]==1): continue
        dp[i]=swag.sum()+1

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

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

    print(*ans)
resolve()

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'))
    if s[-1] == "1":
        print(-1)
    else:
        now = n
        ans = []
        while True:
            b = False
            for j in range(now - m, now):
                if 0 <= j < n:
                    if s[j] != "1":
                        b = True
                        ans.append(now - j)
                        now = j
                        if j == 0:
                            ans.reverse()
                            print(*ans)
                            exit()
                        break
            if not b:
                print(-1)
                exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

from collections import deque
q = deque()

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

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

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

Submission status: Accepted

Solution code:
from collections import Counter

mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft

s = ['SUN', 'MON','TUE','WED','THU','FRI','SAT']

def main():
    n, m = map(int, input().split())
    s = input()
    s = list(reversed(s))
    i = 0
    ans = []
    while i < n:
        next = i
        for j in range(i+1, min(i+m+1, n+1)):
            if s[j] == '0':
                next = j
        if next == i:
            print(-1)
            return
        ans.append(next-i)
        i = next
    print(' '.join(str(i) for i in reversed(ans)))
main()

Submission status: Accepted

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
s = input()
ind = n
ls = []
while ind > 0:
    flg = False
    for i in range(min(m, ind), 0, -1):
        if s[ind - i] == "0":
            ind -= i
            flg = True
            break
    if not flg:
        ls = []
        i = -1
        ind = 0
    ls.append(str(i))
print(" ".join(ls[::-1]))

Submission status: Accepted

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

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

ans = []

now = n
while now != 0:
    tmp = False
    for i in range(m, 0, -1):
        if now-i >= 0 and s[now-i] == '0':
            tmp = True
            now -= i
            ans.append(i)
            break
    if not tmp:
        print(-1)
        sys.exit()
print(*ans[::-1])

Submission status: Accepted

Solution code:
def solve(n, m, s):
    if s.find("1"*m) >= 0:
        return -1
    s = s[::-1]
    i = 0
    path = []
    while i < n:
        for j in range(min(m, n-i), 0, -1):
            ni = i+j
            if s[ni] == "0":
                i = ni
                path.append(j)
                break
    return " ".join(map(str, path[::-1])) 

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

Submission status: Accepted

Solution code:
def solve(n, m, s):
    cnt = 0
    for i in range(1, n+1):
        if (s[i-1] == "0") and (s[i] == "1"):
            cnt = 1
        elif (s[i-1] == "1") and (s[i] == "1"):
            cnt += 1
        if cnt >= m:
            return -1
    s = s[::-1]
    i = 0
    path = []
    while i < n:
        for j in range(min(m, n-i), 0, -1):
            ni = i+j
            if s[ni] == "0":
                i = ni
                path.append(j)
                break
    return " ".join(map(str, path[::-1]))

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

Submission status: Accepted

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

class SegmentTree(object):
    def __init__(self,A,dot,e):
        n=2**((len(A)-1).bit_length())
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__node=[e]*(2*n)
        for i in range(len(A)):
            self.__node[i+n]=A[i]
        for i in range(n-1,-0,-1):
            self.__node[i]=dot(self.__node[2*i],self.__node[2*i+1])

    def update(self,i,c):
        i+=self.__n
        node=self.__node
        node[i]=c
        while(i!=1):
            i//=2
            node[i]=self.__dot(node[2*i],node[2*i+1])

    def sum(self,l,r):
        vl,vr=self.__e,self.__e
        l+=self.__n; r+=self.__n
        while(l<r):
            if(l%2==1):
                vl=self.__dot(vl,self.__node[l])
                l+=1
            l//=2
            if(r%2==1):
                r-=1
                vr=self.__dot(self.__node[r],vr)
            r//=2
        return self.__dot(vl,vr)

def resolve():
    n,m=map(int,input().split())
    S=list(map(lambda x:int(x),input()))
    dp=[INF]*(n+1)
    dp[-1]=0
    tree=SegmentTree(dp,min,INF)
    for i in range(n-1,-1,-1):
        if(S[i]): continue
        s=tree.sum(i,min(i+m+1,n+1))
        dp[i]=s+1
        tree.update(i,s+1)

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

    now=0
    val=dp[0]
    path=[]
    for i,x in enumerate(dp):
        if(x==INF): continue
        if(x<val):
            path.append(i-now)
            now=i
            val=x

    print(*path)
resolve()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
S = list(input())[::-1]
memo = [False]*n
cur = 0
i = 0
ans = []
while i < n:
    for j in range(min(m,n-i),0,-1):
        # print(i,j)
        if S[i+j] == "0":
            ans.append(str(j))
            i += j
            break
        if memo[i+j]:
            ans = -1
            break
        memo[i+j] = True
    if ans == -1:
        break
    # print(S[i:])
print(*ans[::-1]) if ans != -1 else print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
ans = True
res = []
i = n
while i > 0:
    flag = 0
    for j in range(max(0, i - m), i):
        if s[j] == '0':
            flag = 1
            res.append(i - j)
            i = j
            break
    if flag == 0:
        ans = False
        break
if ans == False:
    print(-1)
else:
    for i in range(len(res) - 1, -1, -1):
        print(res[i])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
ans = True
res = []
now = n + 1
for i in range(n, 0, -1):
    flag = 0
    if i > now:
        continue
    for j in range(max(0, i - m), i):
        if s[j] == '0':
            flag = 1
            res.append(i - j)
            now = j
            break
    if flag == 0:
        ans = False
        break
if ans == False:
    print(-1)
else:
    for i in range(len(res) - 1, -1, -1):
        print(res[i])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
ans = True
res = []
now = n + 1
for i in range(n, 0, -1):
    flag = 0
    if i > now:
        continue
    for j in range(max(0, i - m), i):
        if s[j] == '0':
            flag = 1
            res.append(i - j)
            now = j
            break
    if flag == 0:
        ans = False
        break
if ans == False:
    print(-1)
else:
    for i in range(len(res) - 1, -1, -1):
        print(res[i], end=' ')

Submission status: Accepted

Solution code:
N, M = [int(item) for item in input().split()]
S = input()
a=[]
s = S
n = N
while n > 0:
    for i in range(M, 0, -1):
        can = False
        if n>=i and s[n-i] == '0':
            a.append(i)
            s = s[:n-i+1]
            n -= i
            can = True
            break
    if (not can) and len(s)>1:
        print(-1)
        a=[]
        break
a=a[-1::-1]
if len(a):
    print(*a)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
h=input()

cnt=0
for i in range(n):
	if h[i]=="1":
		cnt+=1
	else:
		cnt=0
	if cnt>=k:
		print(-1)
		exit()

h=h[::-1]
h+="0"
idx=0
ans=[]
while 1:
	if idx+k>=n:
		ans.append(n-idx)
		break
	for i in range(k,0,-1):
		if h[idx+i]=="0":
			ans.append(i)
			idx+=i
			break
ans=reversed(ans)
print(" ".join([str(x) for x in ans]))

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    s = input()
    d = [float("inf")]*(n+1)
    d[n] = 0
    i = n
    k = 1
    mi = n
    while i >= 0:
        pre = i
        i = mi
        i -= m
        for j in range(m):
            x = i+j
            if x >= 0:
                if s[x] == "0":
                    d[x] = k
                    if x < mi:
                        mi = x
        if pre == i:
            print(-1)
            return
        k += 1
    q = []
    for i in range(n+1):
        heappush(q,(-d[i],i))
    ans = [0]
    x = 0
    dx = d[0]
    while q:
        di,i = heappop(q)
        if i <= x:
            continue
        di *= -1
        if dx-1 == di:
            dx = di
            x = i
            ans.append(i)
    a = [ans[i+1]-ans[i] for i in range(len(ans)-1)]
    print(*a)
    return

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

def dijkstra_path(s, edges):
    dist = [INF for i in range(len(edges))]
    dist[s], h, p = 0, [], [-1]*len(edges)
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in edges[v]:
            tmp = dv+cost
            if tmp < dist[u]:
                dist[u] = tmp
                p[u] = v
                heappush(h, (tmp, u))
    return dist, p

N, M = map(int, input().split())
S = input()
ids = []
for i, x in enumerate(S):
    if x == '0':
        ids.append(-i)
ids = ids[::-1]
l = len(ids)
es = [[] for i in range(N+1)]
for i in range(N, 0, -1):
    es[i].append((-ids[min(l-1, bisect_right(ids, -i+M)-1)], 1))
d, p = dijkstra_path(N, es)
if d[0] == INF:
    print(-1)
    exit()
vs = []
v = 0
while v != -1:
    vs.append(v)
    v = p[v]
ans = [vs[i+1]-vs[i] for i in range(len(vs)-1)]
print(*ans, sep = ' ')

Submission status: Accepted

Solution code:
n,m = [int(i) for i in input().split()]
s = input()
p = n
q = []

while p!=0:
    frag = True
    for i in range(max(p-m,0),p):
        if s[i]=='0':
            q.append(p-i)
            p=i
            frag = False
            break
    if frag:
        q=[]
        print(-1)
        break
        
for i in reversed(q):
    print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M=map(int,input().split());S=input()[:-1]
if S.find("1"*M)>0:
  print(-1)
  exit()
k=[N+1]*(N+1)
k[0]=N
c=1
for i in range(N-1,-1,-1):
  if int(S[i])==0:
    if k[c-1]-i <= M:
      k[c]=i
    else:
      c+=1
      k[c]=i

print(*[j-i for i,j in zip(k[c::-1],k[c-1::-1])])

Submission status: Accepted

Solution code:
# swag
from collections import deque
class SWAG_Stack():
    def __init__(self, F):
        self.stack1 = deque()
        self.stack2 = deque()
        self.F = F
        self.len = 0

    def push(self, x):
        if self.stack2:
            self.stack2.append((x, self.F(self.stack2[-1][1], x)))
        else:
            self.stack2.append((x, x))
        self.len += 1

    def pop(self):
        if not self.stack1:
            while self.stack2:
                x, _ = self.stack2.pop()
                if self.stack1:
                    self.stack1.appendleft((x, self.F(x, self.stack1[0][1])))
                else:
                    self.stack1.appendleft((x, x))
        self.stack1.popleft()
        self.len -= 1

    def sum_all(self):
        if self.stack1 and self.stack2:
            return self.F(self.stack1[0][1], self.stack2[-1][1])
        elif self.stack1:
            return self.stack1[0][1]
        elif self.stack2:
            return self.stack2[-1][1]
        else:
            raise IndexError

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

stack = SWAG_Stack(min)
stack.push((0,n))
turn = [-1]*(n+1)
turn[-1] = 0
for i in range(n-1, -1, -1):
    if s[i] == "1":
        stack.push((float("inf"), i))
    else:
        cost, ind = stack.sum_all()
        if cost == float("inf"):
            break
        turn[i] = cost+1
        stack.push((cost+1, i))
    if stack.len > m:
        stack.pop()
# print(turn)

if turn[0] == -1:
    print(-1)
    exit()
prev_turn=turn[0]
prev_ind = 0
ans = []
for i in range(1, n+1):
    if prev_turn-turn[i] == 1:
        ans.append(i-prev_ind)
        prev_ind = i
        prev_turn = turn[i]
print(*ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

heap = [(0,n)]
turn = [-1]*(n+1)
turn[-1] = 0
for i in range(n-1, -1, -1):
    if s[i] == "1":
        continue
    while heap and heap[0][1]-i>m:
        heappop(heap)
    if not heap:
        break
    cnt, prev = heap[0]
    turn[i] = cnt+1
    heappush(heap, (turn[i], i))

if turn[0] == -1:
    print(-1)
    exit()
prev_turn=turn[0]
prev_ind = 0
ans = []
for i in range(1, n+1):
    if prev_turn-turn[i] == 1:
        ans.append(i-prev_ind)
        prev_ind = i
        prev_turn = turn[i]
print(*ans)

Submission status: Accepted

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

if __name__ == '__main__':
    p_f_2()

Submission status: Accepted

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

N,M=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

L=[]    #答えの配列の逆順
for _ in range(N):
    for m in range(M,0,-1):
        if 0<=N-m and S[N-m]=="0":
            L.append(m)
            N-=m
            break
    else:
        break
        
if N!=0:
    print -1
else:
    print " ".join(map(str,L[::-1]))

Submission status: Accepted

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

N,M=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

L=[]    #答えの集合
for _ in range(N):
    for m in range(M,0,-1):
        if 0<=N-m and S[N-m]=="0":
            L.append(m)
            N-=m
            break
    else:
        break
        
if N!=0:
    print -1
else:
    print " ".join(map(str,L[::-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#


def main():
    N, M = mis()
    S = input()

    ans = []
    r = N
    l = max(r - M, 0)
    while r > 0:
        for i in range(l, r):
            if S[i] == '0':
                ans.append(r - i)
                r = i
                l = max(r - M, 0)
                break
        else:
            print(-1)
            return
    ans.reverse()
    print(*ans, sep=' ')


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC146 F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

i = 0
cnt = 0
M = 0
while i < n+1:
    if s[i] == '1':
        cnt += 1
        M = max(M,cnt)
    else:
        cnt = 0
    i += 1
if M >= m:
    print(-1)
    quit()

lst = []
now = n
while now > 0:
    if now - m <= 0:
        lst.append(now)
        now -= m 
    else:
        for j in range(1,m+1)[::-1]:
            if s[now-j] == '0':
                lst.append(j)
                now -= j
                break
print(*lst[::-1])

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
S=input()
j=N
ans=deque()
while j>0:
    for i in range(M,0,-1):

        if j-i==0:
            ans.appendleft(i)
            print(*ans)

        elif j-i<0:
            continue
        if S[j-i]=="0":
            ans.appendleft(i)
            j-=i
            break
        if i==1 and S[j-i]=="1":
            print(-1)
            exit()

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()
i=N
flg=0
ans=[]
while i>0:
  j=M
  if i-M<0:
    ans.append(i)
    i=0
  else:
    while j>=0:
      if j>0 and S[i-j] == '0':
        ans.append(j)
        i-=j
        j=0
      elif j==0:
        flg=1
        i=0
      j-=1
if flg==1:
  print(-1)
else:
  print(*reversed(ans))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
ans=''
i=N
flg=0
while i>0:
  j=M
  if i-M<0:
    ans=str(i)+' '+ans
    i=0
  else:
    while j>=0:
      if j>0 and S[i-j] == '0':
        ans=str(j)+' '+ans
        i-=j
        j=0
      elif j==0:
        flg=1
        i=0
      j-=1
if flg==1:
  print(-1)
else:
  print(ans)