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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


from heapq import heappush, heappop

def Dijkstra(num, start, s, m):
    dist = [float("inf") for i in range(num)]
    x = -1
    dist[0] = 0
    for i in range(num):
        if x > i:
            continue
        a = dist[i]
        for k in range(m):
            k += 1
            if i + k >= num:
                return dist
            if s[i + k] == "1":
                continue
            dist[i + k] = a + 1
            x = i + k
    return dist


#solve
def solve():
    n, m = LI()
    s = S()
    d = Dijkstra(n + 1, 0, s, m)
    q = deque([n])
    if d[-1] == inf:
        print(-1)
        return
    ans = []
    while q:
        a = q.pop()
        x = d[a]
        for i in range(min(a, m), 0, -1):
            if x - 1 == d[a - i]:
                q.append(a - i)
                ans.append(i)
                break
    ans = ans[::-1]
    print(" ".join(map(str, ans)))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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

global min_rireki,ans
min_rireki = float("inf")
ans = []
global get_point
get_point = [float("inf") for i in range(n+1)]
get_point[0] = 0

def dfs(pos, rireki):
    global ans
    if pos == n:
        if len(rireki) < min_rireki:
            ans = rireki
    else:
        for i in range(1,m+1):
            if pos + i <= n:
                if s[pos+i] == "0":
                    if get_point[pos+i] - 1 > len(rireki):
                        dfs(pos+i, rireki+[i])
                        get_point[pos+i] = len(rireki) + 1

dfs(0,[])
if ans == []:
    print(-1)
else:
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


from heapq import heappush, heappop

def Dijkstra(num, start, s, m):
    dist = [float("inf") for i in range(num)]
    x = -1
    dist[0] = 0
    for i in range(num):
        if x > i:
            continue
        a = dist[i]
        for k in range(m):
            k += 1
            if i + k >= num:
                x = num
                break
            if s[i + k] == "1":
                continue
            dist[i + k] = a + 1
            x = i + k
    return dist


#solve
def solve():
    n, m = LI()
    s = S()
    d = Dijkstra(n + 1, 0, s, m)
    q = deque([n])
    if d[-1] == inf:
        print(-1)
        return
    ans = []
    while q:
        a = q.pop()
        x = d[a]
        for i in range(min(a, m), 0, -1):
            if x - 1 == d[a - i]:
                q.append(a - i)
                ans.append(i)
                break
    ans = ans[::-1]
    print(" ".join(map(str, ans)))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

N,M = map(int, input().split())		# 5 7 2
S = input()		# 文字列の入力  abcdefg...

x=N

if S[x]=='1':
	print(-1)
	exit(0)


ans=[]

while x>0:
	for i in range(M,0,-1):
		#p("x,i,ans, ",x,i,ans)
		
		if x-i<0: continue
		
		if S[x-i]=='0':
			ans = [i] + ans
			x-=i
			break

	else:
		print(-1)
		exit(0)

print(*ans)

Submission status: Time Limit Exceeded

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

def copy(a):
    return [i.copy() if type(i) is list else i for i in a]
s = input()
path = [[0, (), 0]]
for i in range(1, n + 1):
    if s[i] == "0":
        while True:
            if not path:
                print(-1)
                exit()
            a = heapq.heappop(path)
            if a[2] + m >= i:
                break
        if a[2] + m != i:
            heapq.heappush(path, copy(a))
        a[0] += 1
        a[1] += (i-a[2],)
        a[2] = i
        heapq.heappush(path, copy(a))
print(" ".join([str(i) for i in a[1]]))

Submission status: Time Limit Exceeded

Solution code:


from sys import exit


ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n,m = mi()
    s = list(input())

    op = [0 for i in range(n+1)]

    cnt = 0
    flag = False
    place = []
    for i in range(len(s)):
        if flag and s[i] == '1':
            cnt+=1
            if cnt == m:
                print(-1)
                exit()
        elif s[i] == '1':
            flag = True
            cnt+=1
        else:
            flag = False
            cnt = 0


    r = 0
    for l in range(n+1):
        if s[l] == '0':
            for i in range(r-l+1,m+1):
                if l+i > n:
                    break
                op[l+i] = i
            r = l+m
        if r<n+1:
            break
        





    ans = []
    op = op[::-1]
    np = 0
    flag = True
    while np < n:
        ans.append(op[np])
        np+=op[np]


    print(*ans[::-1])

    


        


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M  = [int(i) for i in input().split()]
    S  = [int(i) for i in input()]
    cur = [0]
    while cur:
        nxt = []
        for loc in cur:
            if loc == N:
                a = []
                while loc > 0:
                    w = S[loc]
                    loc -= w
                    a.append(w)
                return ' '.join(str(j) for j in reversed(a))
            for i in range(1, M + 1):
                nloc = loc + i
                if nloc > N or S[nloc]:
                    continue
                S[nloc] = i
                nxt.append(nloc)
        cur = nxt
    return '-1'


print(main())

Submission status: Time Limit Exceeded

Solution code:

from sys import exit


ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n,m = mi()
    s = list(input())

    op = [0 for i in range(n+1)]

    cnt = 0
    flag = False
    place = []
    for i in range(len(s)):
        if flag and s[i] == '1':
            cnt+=1
            if cnt == m:
                print(-1)
                exit()
        elif s[i] == '1':
            flag = True
            cnt+=1
        else:
            place.append([])
            flag = False
            cnt = 0


    l = 0
    r = 0
    while r<n+1:
        if s[l] == '0':
            for i in range(r-l+1,m+1):
                if l+i > n:
                    break
                op[l+i] = i
            r = l+m
        l+=1
        





    ans = []
    op = op[::-1]
    np = 0
    flag = True
    while np < n:
        ans.append(op[np])
        np+=op[np]


    print(*ans[::-1])

    


        


main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re
import heapq


from copy import deepcopy
import itertools

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n,m = mi()
    s = list(input())

    op = [0 for i in range(n+1)]

    cnt = 0
    flag = False
    place = []
    for i in range(len(s)):
        if flag and s[i] == '1':
            cnt+=1
            if cnt == m:
                print(-1)
                exit()
        elif s[i] == '1':
            flag = True
            cnt+=1
        else:
            place.append([])
            flag = False
            cnt = 0


    l = 0
    r = 0
    while r<n+1:
        if s[l] == '0':
            for i in range(r-l+1,m+1):
                if l+i > n:
                    break
                op[l+i] = i
            r = l+m
        l+=1
        





    ans = []
    op = op[::-1]
    np = 0
    flag = True
    while np < n:
        ans.append(op[np])
        np+=op[np]


    print(*ans[::-1])

    


        


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M  = [int(i) for i in input().split()]
    S  = [i == '1' for i in input()]
    cur = [(0, [])]
    while cur:
        nxt = []
        for loc, hist in cur:
            if loc == N:
                return ' '.join(str(j) for j in hist)
            for i in range(1, M + 1):
                nloc = loc + i
                if nloc > N or S[nloc]:
                    continue
                S[nloc] = True
                nxt.append((nloc, hist + [i]))
        cur = nxt
    return '-1'


print(main())

Submission status: Time Limit Exceeded

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re
import heapq


from copy import deepcopy
import itertools

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n,m = mi()
    s = list(input())

    op = [0 for i in range(n+1)]

    l = 0
    r = 0
    while r<n+1:
        if s[l] == '0':
            for i in range(r-l+1,m+1):
                if l+i > n:
                    break
                op[l+i] = i
            r = l+m
        l+=1


    cnt = 0
    flag = False
    place = []
    for i in range(len(s)):
        if flag and s[i] == '1':
            cnt+=1
            if cnt == m:
                print(-1)
                exit()
        elif s[i] == '1':
            flag = True
            cnt+=1
        else:
            place.append([])
            flag = False
            cnt = 0



    ans = []
    op = op[::-1]
    np = 0
    flag = True
    while np < n:
        ans.append(op[np])
        np+=op[np]


    print(*ans[::-1])

    


        


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M  = [int(i) for i in input().split()]
    S  = [i == '1' for i in input()]
    cur = [(0, [])]
    while cur:
        nxt = []
        for loc, hist in cur:
            for i in range(1, M + 1):
                nloc = loc + i
                if nloc == N:
                    return ' '.join(str(j) for j in hist + [i])
                elif nloc > N:
                    continue
                elif S[nloc]:
                    continue
                S[nloc] = True
                nxt.append((nloc, hist + [i]))
        cur = nxt
    return '-1'


print(main())

Submission status: Time Limit Exceeded

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

def copy(a):
    return [i[:] if type(i) is list else i for i in a]
s = input()
path = [[0, [], 0]]
for i in range(1, n + 1):
    if s[i] == "0":
        while True:
            if len(path) == 0:
                print(-1)
                exit()
            a = heapq.heappop(path)
            if a[2] + m >= i:
                break
        if a[2] + m != i:
            heapq.heappush(path, copy(a))
        a[0] += 1
        a[1] += [i-a[2]]
        a[2] = i
        heapq.heappush(path, copy(a))
print(" ".join([str(i) for i in a[1]]))

Submission status: Time Limit Exceeded

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


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

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

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

      if values[j] is not None:
        break

      values[j] = i

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

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

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

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


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

dp = [float('inf')]*N
dp[-1] = 0

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

dp += [float('inf')]*(M+1)
res = []
i = 0
while i < N-1:
    t = dp[i]
    s = min(k for k in range(1,M+1) if dp[i+k]==t-1)
    res.append(s)
    i += s
print(*res)

Submission status: Time Limit Exceeded

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re
import heapq


from copy import deepcopy
import itertools

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n,m = mi()
    s = list(input())[::-1]

    cnt = 0
    flag = False

    for i in range(len(s)):
        if flag and s[i] == '1':
            cnt+=1
            if cnt == m:
                print(-1)
                exit()
        elif s[i] == '1':
            flag = True
            cnt+=1
        else:
            flag = False
            cnt = 0



    ans = []
    np = 0
    flag = True
    while(flag):
        for i in range(m,0,-1):
            if np+i > n:
                continue
            elif np+i == n:
                np = np+i
                ans.append(i)
                flag = False
                break
            elif s[np+i] == '1':
                continue
            elif s[np+i] == '0':
                np = np+i
                ans.append(i)
                break


    print(*ans[::-1])

    


        


main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def solve(n, m, s):
    q = [(0, 0)]
    curr = None
    for i in range(1, n + 1):
        if s[i] == '1':
            continue
        left_limit = max(0, i - m)
        while q and q[0][-1] < left_limit:
            heappop(q)
        if not q:
            return (-1,)
        prev = q[0]
        dice = i - prev[-1]
        curr = (prev[0] + 1,) + prev[1:-1] + (dice, i)
        heappush(q, curr)

    return curr[1:-1]


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

Submission status: Time Limit Exceeded

Solution code:
class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


def solve(n, m, s):
    INF = 10 ** 18
    sgt = SegTreeMin(n + 1, (INF,))
    sgt.update(0, (0, 0))
    for i in range(1, n + 1):
        if s[i] == '1':
            continue
        r = i
        l = max(0, i - m)
        prev = sgt.get_min(l, r)
        if prev[0] == INF:
            return (-1,)
        dice = i - prev[-1]
        curr = (prev[0] + 1,) + prev[1:-1] + (dice, i)
        sgt.update(i, curr)
    return sgt.get_min(n, n + 1)[1:-1]


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

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
n,m = ma()
s = input()
dp = [-1]*(n+1) #dp[i]:: i番目にたどり着く最小コスト
dp[0]=0
r=0
while r<=n-1:
    l=0
    tmp=0
    while l+1<=m and r+l+1<=n:
        l+=1
        if s[r+l]=="0":
            tmp=l
            dp[r+l]=dp[r]+1
    r+=tmp
    #if r==n:break
    if tmp==0:
        print(-1)
        exit()
d = dp[-1]
rt = []
dp = dp[::-1]
r=0
while r<=n-1:
    l=0
    tmp=0
    while l+1<=m and r+l+1<=n:
        l+=1
        if dp[r+l]==d-1:
            tmp=l
    rt.append(tmp)
    d-=1
    r+=tmp
print(*reversed(rt))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()

# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16580070


class SegmentTree:

    __slots__ = ["func", "e", "original_size", "n", "data"]

    def __init__(self, length_or_list, func=max, e=-10**18):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.n = 1 << ((length_or_list - 1).bit_length())
            self.data = [self.e] * (self.n*2)
        else:
            self.original_size = len(length_or_list)
            self.n = 1 << ((self.original_size - 1).bit_length())
            self.data = [self.e] * self.n + length_or_list + \
                [self.e] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(
                self.data[2*index], self.data[2*index+1])
            index //= 2

    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)

    def all_folded(self):
        return self.data[1]

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

    def max_right(self, l, f):
        # assert f(self.e)
        if l >= self.original_size:
            return self.original_size
        l += self.n
        left_folded = self.e
        while True:
            # l //= l & -l
            while l % 2 == 0:
                l //= 2
            if not f(self.func(left_folded, self.data[l])):
                while l < self.n:
                    l *= 2
                    if f(self.func(left_folded, self.data[l])):
                        left_folded = self.func(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.func(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size

    # 未verify
    def min_left(self, r, f):
        # assert f(self.e)
        if r == 0:
            return 0
        r += self.n
        right_folded = self.e
        while True:
            r //= r & -r
            if not f(self.func(self.data[r], right_folded)):
                while r < self.n:
                    r = 2 * r + 1
                    if f(self.func(self.data[r], right_folded)):
                        right_folded = self.func(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            if r == r & -r:
                break
        return 0


def minindex(x, y):
    if x[0] <= y[0]:
        return x
    else:
        return y


def main():
    n, m = map(int, input().split())
    S = list(map(lambda x: 0 if x == '0' else 10**10, list(input())))
    roots = [10**10]*(n+1)
    for i in range(1, min(m+2, n+1)):
        if S[i] < 10**9:
            S[i] = 1
            roots[i] = 0
    S = [[s, i] for i, s in enumerate(S)]
    seg = SegmentTree(S, minindex, [10**12, 10**12])
    for i in range(m+1, n+1):
        if S[i][0] < 10**9:
            dist, masu = seg.folded(i-m, i)
            roots[i] = masu
            seg.replace(i, [dist+1, i])
    #print(seg.data[16:])
    #print(roots)
    if seg.folded(n, n+1)[0] > 10**9:
        print(-1)
    else:
        ans = []
        while n > 0:
            ans.append(n-roots[n])
            n = roots[n]
        print(*ans[::-1], sep=" ")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

"""
スタートから貪欲に考えようとすると
「最短で行くために大きい目を出したい」と
「辞書順最小のために小さい目を出したい」が共存してやりづらい

ゴールから貪欲に考える（出来るだけ多く戻る）と考えると
「最短で行くために大きい目を出したい」と
「辞書順最小のために、最後の手を出来るだけ小さくしたい
 -> 後ろから考えて、大きい目を出せば良い」となり
貪欲に解ける
"""
# 出した目の値（逆順）
ans = []
# 現在の位置（ゴールを0、スタートをNとする）
now = 0

while True:
    # Mだとオーバーしてしまう場合(ちょうど終わる場合も含む)
    # 最後の目を記録して終了
    if now + M >= N:
        ans.append(N - now)
        break

    # Mマス進むと仮定する
    step = M
    # 行き先がゲームオーバーなら、stepをデクリメント
    while S[now + step] == '1':
        step -= 1
        # step = M,M-1,...,1がダメならこれ以上進めないので終了
        if step == 0:
            print(-1)
            exit()

    now += step
    ans.append(step)

print(*ans[::-1])

Submission status: Accepted

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

n, m = map(int, input().split())
s = input()
s = s[::-1]
INF = 2*n

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

dp = [-1] * (n+1)
nw = 0
st = 0
nst = 0
ret = []
while nw < (n+1):
    if s[nw]=='1':
        dp[nw] = INF
    else:
        dp[nw] = dp[st] + 1
        nst = nw
    nw += 1
    if nw == n+1:
        ret.append(nst-st)
    elif nw > st + m:
        ret.append(nst-st)
        st = nst
print(' '.join(map(str,ret[::-1])))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input()
if N <= M:
  print(N)
  exit()
if '1'*M in S:
  print(-1)
  exit()

from collections import deque
count = deque([])
for k in range(M+1):
  if S[k] == '1':
    count.append(-1)
  else:
    count.append(k)
sgn = deque([])
k = 0
while k < N:
  k += 1
  if S[k] == '0':
    sgn.append(M)
  else:
    d = 0
    while k < N:
      if S[k] == '1':
        k += 1
        d += 1
        continue
      else:
        break
    while d > 0:
      sgn.append(M-d)
      d -= 1
    sgn.append(M)
now = M
while now < N:
  now += 1
  a = sgn.popleft()
  if S[now] == '1':
    count.append(-1)
  else:
    count.append(a)
count = list(count)  
c = 0
ans = ''
while c < N:
  ans = str(count[-1-c]) + ' ' + ans
  c += count[-1-c]

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N, M = LI()
    S = SL()

    ans = []
    tmp = 0
    checkpoint = -1

    for e in S[:-1][::-1]:
        tmp += 1
        if e == "0":
            if tmp >= M:
                ans.append(tmp)
                tmp = 0
                checkpoint = -1
            else:
                checkpoint = tmp
        else:
            if tmp >= M:
                if checkpoint == -1: break
                ans.append(checkpoint)
                tmp -= checkpoint
                checkpoint = -1
    else:
        if tmp > 0:
            ans.append(tmp)
        print(*ans[::-1])
        return
    print(-1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[int(s) for s in input()][::-1]
i=0
k=m
cnt=0
a=[]
while i<n:
  j=-1
  while i<n and k:
    k-=1
    i+=1
    if s[i]==0:j=i
  if j==-1:
    print(-1)
    exit()
  a+=[j]
  k=m-i+j
  cnt+=1
for i in range(len(a)-1,0,-1):
  a[i]-=a[i-1]
print(*a[::-1])

Submission status: Accepted

Solution code:
from sys import exit

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

res = []
pos = 0
while True:
    if pos + m >= n:
        res.append(n - pos)
        break

    step = m
    while s[pos + step] == '1':
        step -= 1
        if step == 0:
            print(-1)
            exit()
    
    pos += step
    res.append(step)
    
print(*res[::-1])

Submission status: Accepted

Solution code:
from sys import exit

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

res = []
pos = 0
while True:
    if pos + m >= n:
        res.append(n - pos)
        break

    step = m
    while s[pos + step] == '1':
        step -= 1
        if step == 0:
            print(-1)
            exit()
    
    pos += step
    res.append(step)
    
print(*res[::-1], sep=' ')

Submission status: Accepted

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

"""
ゴール側から考えれば、自然と辞書順最小になる。（気がする）
前処理で各セーフマスから最も近い前方のセーフマスの位置を求めておく。
nxSafe[i] =>　ゴールからスタートに進むとして、ゴールからiマス目の次のセーフゾーンのインデックス
"""
nxSafe = [None]*(N+1)
safe = N
for i in range(N-1,-1,-1):
    if RS[i] == "0":
        nxSafe[i] = safe
        safe = i

cur = 0
ans = []
while cur < N:
    tmp = cur
    while True:
        if tmp == N:
            break
        if nxSafe[tmp] - cur <= M:
            tmp = nxSafe[tmp]
        else:
            break
    if cur == tmp:
        print(-1)
        exit()
    ans.append(str(tmp-cur))
    cur = tmp
ans = ans[::-1]
print(" ".join(ans))

Submission status: Accepted

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

index = N
count = 0
history = []
while index > 0:
    start = max(0, index - M)
    for i, c in enumerate(S[start:index], start=start):
        if c == '0':
            history.append(index - i)
            index = i
            count += 1
            break
    else:
        print(-1)
        exit()

print(*history[::-1])