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:
n, m = map(int, input().split())
s = input()
dp = [[-1, float("inf")] for _i in range(n+1)]
dp[0] = [0,0]
for i in range(1, n+1):
    for j in range(max(0,i-m), i):
        if s[j]=="0" and dp[j][0] >= 0:
            if dp[i][1] > dp[j][1]+1:
                dp[i][0] = j
                dp[i][1] = dp[j][1] + 1 
            elif dp[i][1] == dp[j][1]+1:
                dp[i][0] = min(dp[i][0], j)
if dp[n][0] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p][0]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
s = s[::-1]
if s[0] == "1":
    print(-1)
    exit()
pre = [-1] * (n + 1)
stack = [0]
while stack:
    now = stack.pop()
    if now == n:
        break
    for i in range(1, m + 1):
        tsugi = now + i
        if tsugi > n:
            continue
        if s[tsugi] == "1":
            continue
        pre[tsugi] = now
        stack.append(tsugi)
else:
    print(-1)
    exit()
ato = n
mae = pre[n]
ans = []
while mae >= 0:
    ans.append(ato - mae)
    ato = mae
    mae = pre[ato]
print(*ans, sep=" ")

Submission status: Time Limit Exceeded

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

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(len(bin(b))-2)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])

Submission status: Time Limit Exceeded

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

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = (1<<M) -1
for i in range(N+1):
  b = ((b<<1) + S[i])&mask
  max_n.append(len(bin(mask-b))-2)

  
now = N
deme = []
while now > 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

Submission status: Time Limit Exceeded

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

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N+1):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(len(bin(b))-2)

now = N
deme = []
while now > 0:
  x = max_n[now]
  if x == 0:
    print(-1)
    exit()
  now = now-x
  deme.append(x)
print(*deme[::-1])

Submission status: Time Limit Exceeded

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

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N+1):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(len(bin(b))-2)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

Submission status: Time Limit Exceeded

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

import math

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

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(len(bin(b))-2)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

Submission status: Time Limit Exceeded

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

from collections import defaultdict
route = defaultdict(list)

for i in range(n):
    for j in range(1,min(m+1,n+1-i)):
        if s[i+j]==1:
            dp[i+j] = INF
            continue
        if dp[i+j] > dp[i]+1:
            dp[i+j] = dp[i]+1
            route[i+j]=(i,j)

if dp[n]==INF:
    print(-1)
    exit()

i=0
now,m = route[n]
ans = [m]
while now > 0:
    now,m = route[now]
    ans.append(m)

ans.reverse()

print(*ans,sep=' ')

Submission status: Time Limit Exceeded

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

from collections import defaultdict
route = defaultdict(list)

for i in range(n):
    for j in range(1,m+1):
        if i+j >= n+1: break
        if s[i+j]==1:
            dp[i+j] = INF
            continue
        if dp[i+j] > dp[i]+1:
            dp[i+j] = dp[i]+1
            route[i+j]=(i,j)

if dp[n]==INF:
    print(-1)
    exit()

i=0
now,m = route[n]
ans = [m]
while now > 0:
    now,m = route[now]
    ans.append(m)
    
ans.reverse()

print(*ans,sep=' ')

Submission status: Time Limit Exceeded

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

sl = sl[::-1]

dp = [float("inf") for _ in range(n+1)]
before = [-1 for _ in range(n+1)]
dp[0] = 0

for i in range(n):
    for j in range(1, m+1):
        if i + j <= n:
            if dp[i] + 1 <= dp[i+j] and sl[i+j] == "0":
                dp[i+j] = dp[i] + 1
                before[i+j] = i


if dp[-1] == float("inf"):
    print(-1)
    exit()

ansl = []
now = n
while True:
    if before[now] == -1:
        break
    ansl.append(now - before[now])
    now = before[now]

print(*ansl)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
s = readline().rstrip().decode()[::-1]
index = 0
ans = []
for i in range(n):
    for j in range(m, 0, -1):
        if index + j >= n:
            ans = [n - index] + ans
            print(*ans)
            exit()
        if s[index + j] == '0':
            ans = [j] + ans
            index += j
            break
    else:
        print(-1)
        exit()

Submission status: Time Limit Exceeded

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

for i in reversed(range(n-1)):
    if s[i] == "1":
        continue
    for j in range(min(n-1-i, m)):
        # print(i, j)
        if s[i+j+1] == "0":
            dst[i] = min(dst[i], dst[i+j+1]+1)

# print(dst)
if dst[0] == float("inf"):
    print(-1)
else:
    last_idx = 0
    last_num = dst[0]
    ans = []
    for i in range(1, n):
        if dst[i] != float("inf") and dst[i] != last_num:
            ans.append(i - last_idx)
            last_num = dst[i]
            last_idx = i

    print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
n, m = map(int, input().split())
s = input()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
n, m = map(int, input().split())
s = input()

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(n+1):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
n, m = map(int, input().split())
s = input()

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos > -1:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
n, m = map(int, input().split())
s = input()

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos != 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
n, m = map(int, input().split())
s = input()

if n <= m:
    print(n)
    exit()

one_sequence = 0
for i in range(1, n):
    if s[i] == "1":
        one_sequence += 1
        if one_sequence == m:
            print(-1)
            exit()
    else:
        one_sequence = 0

pos = n
ans = ""
while pos > 0:
    for i in range(1, m+1)[::-1]:
        if pos-i < 0:
            continue
        if s[pos-i] != "1":
            ans = str(i) + " " + ans
            pos -= i
            break
print(ans.strip())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
s = input()


inf=float("inf")
#i番目のマスに行くための最小手数と、その出目
from copy import copy
dp = [(0,[])] + [(inf,None) for _ in range(n)]
for i in range(1,n+1):
    if s[i]=="0":
        for j in range(m,0,-1):
            if i-j<0:
                continue
            if dp[i-j][0]<inf:
                dp[i]=(dp[i-j][0]+1,dp[i-j][1]+[j])
                break
if dp[-1][1]:

    print(" ".join(map(str,dp[-1][1])))
else:
    print(-1)

Submission status: Time Limit Exceeded

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

def goal(a):
  if s[a] == "1":
    return -1
  position = a
  cnt1 = 0
  cnt2 = 0
  count = 0
  for i in range(a + 1, n):
    cnt1 += 1
    if s[i] == "0":
      cnt2 = i - position
    if cnt1 == m:
      if cnt2 == 0:
        count = -1
        break
      else:
        position += cnt2
        count += 1
        cnt1 = i - position
  if count == -1:
    return -1
  else:
    count += 1
    return count
  
A = []
B = [0]
C = []
for i in range(n):
  A.append(goal(i))
cnt = A[0]
for i in range(1,n):
  if A[i] == cnt - 1:
    B.append(i)
  if A[i] != -1:
    cnt = A[i]
B.append(n)
for i in range(len(B) - 1):
  C.append(B[i + 1] - B[i])
if goal(0) == -1:
  print(-1)
else:
  print(" ".join(map(str, C)))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
dp = [inf for _ in range(n + 1)] #i手で到達できる場所
dp[0] = 0
arr = [[inf for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    arr.append(0)
    if s[i] == 0:
        for j in reversed(range(1, m + 1)):
            if 0 <= i - j <= n and s[i - j] == 0 and dp[i] >= dp[i - j] + 1:
                dp[i] = dp[i - j] + 1
                arr[i][dp[i - j] + 1] = j
                break
ans = [inf for _ in range(dp[n])]
idx = n
for i in reversed(range(1, dp[n] + 1)):
    ans[i - 1] = arr[idx][i]
    idx -= arr[idx][i]
for i in range(dp[n]):
    ans[i] = str(ans[i])
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = 100#sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
dp = [inf for _ in range(n + 1)] #i手で到達できる場所
dp[0] = 0
arr = [[inf for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    arr.append(0)
    if s[i] == 0:
        for j in range(1, m + 1):
            if 0 <= i - j <= n and s[i - j] == 0 and dp[i] >= dp[i - j] + 1:
                dp[i] = dp[i - j] + 1
                arr[i][dp[i - j] + 1] = j
ans = [inf for _ in range(dp[n])]
idx = n
for i in reversed(range(1, dp[n] + 1)):
    ans[i - 1] = arr[idx][i]
    idx -= arr[idx][i]
for i in range(dp[n]):
    ans[i] = str(ans[i])
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    n,m = map(int,input().split())
    l = list(input())
    l = l[::-1]
    count = [-1]*(n+1)
    count[0] = 0
    check = 1
    i = 0

    while i < n+1:
        if count[i] != -1:
            a = -1
            for j in range(1,m+1):
                if i+j < n+1 and l[i+j] != "1":
                    count[i+j] = check
                    a = i+j
            
            check += 1
            if a == -1:
                print(-1)
                exit()
            else:
                i = a
            
            if count[-1] != -1:
                break
    count = count[::-1]

    ans = []
    a = 0
    for i in range(check-2,-1,-1):
        b = count.index(i)
        ans.append(b-a)
        a = b
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = list(input())
l = l[::-1]
count = [-1]*(n+1)
count[0] = 0
check = 1
i = 0

while i < n+1:
    if count[i] != -1:
        a = -1
        for j in range(1,m+1):
            if i+j < n+1 and l[i+j] != "1":
                count[i+j] = check
                a = i+j
        
        check += 1
        if a == -1:
            print(-1)
            exit()
        else:
            i = a
        
        if count[-1] != -1:
            break
count = count[::-1]

ans = []
a = 0
for i in range(check-2,-1,-1):
    b = count.index(i)
    ans.append(b-a)
    a = b
print(*ans)

Submission status: Time Limit Exceeded

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

INF=10**10
dp = [[INF,[None]] for _ in range(n+1)]

dp[0]= [0,[]]

import copy
def comp(l1,l2):
    for i in range(len(l1)):
        if l1[i] == l2[i]:
            continue
        return l1[i] < l2[i]
    return True

for i in range(n):
    if dp[i][0] == INF:
        continue
    for j in range(1,m+1):
        if i+j > n:
            break
        if s[i+j] == "1":
            continue
        if dp[i+j][0] > dp[i][0]+1:
            dp[i+j][0] = dp[i][0]+1
            his = copy.deepcopy(dp[i][1])
            his.append(j)
            dp[i+j][1] = his
        elif dp[i+j][0] == dp[i][0]+1:
            his = copy.deepcopy(dp[i][1])
            his.append(j)
            if comp(his,dp[i+j][1]):
                dp[i+j][1] = his

#for tmp in dp:
#    print(tmp)
if dp[-1][0] != INF:
    print(*dp[-1][1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

stack = deque([[0, M + 1]])
now = 0
while stack:
    now, d = stack.pop()
    d -= 1
    if not d:
        continue
    if now + d >= N:
        stack.append([now, d - (now + d - N)])
        print(*map(lambda s: s[1], reversed(stack)))
        quit()
    stack.append([now, d])
    if S[now + d] == "0":
        stack.append([now + d, M + 1])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m = map(int, input().split())
s = input()
d = [[str(m) for _ in range(n+1)] for _ in range(n+1)]
d[0] = ["0"]
for i in range(1,n+1):
  for k in range(min(i,m),0,-1):
    if s[i-k] == "0" and len(d[i]) >= len(d[i-k])+1 and int("".join(d[i])) > int("".join(d[i-k]))*10 + k:
      d[i] = copy.deepcopy(d[i-k])
      d[i].append(str(k))
      break
if d[n]==[str(m) for _ in range(n+1)]:
  print(-1)
else:
  print(" ".join(d[n][1:]))

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m = map(int, input().split())
s = input()
d = [[str(m) for _ in range(n+1)] for _ in range(n+1)]
d[0] = ["0"]
for i in range(1,n+1):
  for j in range(1,min(i+1,m+1)):
    if s[i-j] == "0" and len(d[i]) >= len(d[i-j])+1 and int("".join(d[i])) > int("".join(d[i-j]))*10 + j:
      d[i] = copy.deepcopy(d[i-j])
      d[i].append(str(j))
if d[n]==[str(m) for _ in range(n+1)]:
  print(-1)
else:
  print(" ".join(d[n][1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

ans = []
check = []

idx = N
while 0 < idx:
    for i in range(M, -1, -1):
        if idx-i < 0: continue
        if S[idx-i] == '1':
            if idx-i in check: print(-1); sys.exit()
            else: check.append(idx-i)
        else:
            ans.append(i)
            idx -= i
            break

for a in ans[::-1]: print(a)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
S = list(input())
d = [-1] * (N+1)
for i in range(N+1):
    if S[i] == '1':
        d[i] = -99
T = [0]
x = []
while True:
    NT = []
    for i in T:
        for j in range(1,M+1):
            if d[i + j] == -1:
                NT.append(i + j)
                d[i + j] = i
                if i + j == N:
                    p = i
                    x = [j]
                    while p > 0:
                        x.append(p - d[p])
                        p = d[p]
                if i + j >= N:
                    break
        if x!=[]:
            break
    else:
        if T == []:
            break
        T,NT = NT,T
        continue
    break
if x == []:
    print (-1)
else:
    while x != []:
        print (x.pop(),end=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, S: str):

    # 最短手数を求める
    DP = [INF]*(N+1)
    DP[0] = 0
    for i in range(1, N+1):
        if S[i] == "1":
            continue
        for j in range(1, M+1):
            if i-j < 0:
                break
            DP[i] = min(DP[i], DP[i-j]+1)

    if DP[-1] == INF:
        print(-1)
        return
    # 逆順に辿って実際の手を求める
    # 辞書順になるよう、後ろから貪欲に選ぶ
    ans = []
    curr = N
    while curr > 0:
        for i in range(M, 0, -1):
            if curr-i < 0:
                continue
            if curr-i == 0:
                break
            if DP[curr-i] < DP[curr]:
                break
        curr = curr - i
        ans.append(i)
    print(*reversed(ans), sep=" ")

    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)  # type: str
    solve(N, M, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = []
tmp = 0
for i in range(n+1):
    last = tmp
    for j in range(0, m):
        j = m - j
        if tmp + j >= len(s): continue

        if s[tmp + j] == "0":
            tmp += j
            ans.append(str(j))
            break
    if last == tmp and last != len(s)-1:
        ans = -1
        break
if ans != -1:
    ans = ans[::-1]
    ans = ' '.join(ans)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200001)

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

ans = []

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

ans = rest(N, [])

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

Submission status: Time Limit Exceeded

Solution code:
N, M=map(int, input().split())
S=input()
math=['']+['0' if S[i]=='0' else '-1' for i in range(1, N)]+['0']
for i in range(1, min(N+1, M+1)):
  if math[i]=='0':
    math[i]=str(i)
    
i=M+1
while i<N+1:
  if math[i]=='0':
    for j in range(M, 0, -1):
      if math[i-j]!='-1':
        math[i]=math[i-j]+' '+str(j)      
        break
    if math[i]=='0':
      math[i]='-1'
  i+=1
  
print(math[-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
s=input()
p=[([i] if s[i]=="0"else [])for i in range(n+1)]
for i in range(1,n+1):
    p[i]=p[i-1]+p[i]
    if i-p[i][0]>m:
        p[i].pop(0)
    if len(p[i])==0:
        print(-1)
        break
else:
    c=[]
    t=n
    while t!=0:
        q=p[t][0]
        c.append(t-q)
        t=q
    print(*c[::-1])

Submission status: Time Limit Exceeded

Solution code:
import copy


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

# 1-Mの幅優先探索を繰り返す
# 1を踏んだ場合と、
# 手数が少ない経路が存在する場合はそれ以上探索しない
que = []

# 最高到達点
highest = 0

# rootからのデータ投入
for i in range(1, M+1):
    que.append([i])

while True:
    try:
        q = que.pop(0)
    except IndexError:
        # キューが空になってしまう場合、到達できない
        print(-1)
        exit()
    
    # print(q)

    # 現在地点算出
    current = sum(q)
    # ゴールの場合
    if current == N:
        # 出力して終了
        for pos in q:
            print(pos, end=" ")
        print()
        exit()
    # ゲームオーバーの場合
    if S[current] == '1':
        # 積まずに別の探索を行う
        continue
    # 最高地点がすでに到達している場合
    # それ以上進まない
    if current == highest:
        continue
    # 最高地点を更新する
    highest = current
    # 途中の場合、M通りに分岐する
    for i in range(1, M+1):
        q2 = copy.deepcopy(q)
        q2.append(i)
        que.append(q2)

Submission status: Time Limit Exceeded

Solution code:
import copy


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

# 1-Mの幅優先探索を繰り返す
# 1を踏んだ場合と、
# 手数が少ない経路が存在する場合はそれ以上探索しない
que = []

# rootからのデータ投入
for i in range(1, M+1):
    que.append([i])

while True:
    try:
        q = que.pop(0)
    except IndexError:
        # キューが空になってしまう場合、到達できない
        print(-1)
        exit()
    
    # print(q)

    # 現在地点算出
    current = sum(q)
    # ゴールの場合
    if current == N:
        # 出力して終了
        for pos in q:
            print(pos, end=" ")
        print()
        exit()
    # ゲームオーバーの場合
    if S[current] == '1':
        # 積まずに別の探索を行う
        continue
    # 途中の場合、M通りに分岐する
    for i in range(1, M+1):
        q2 = copy.deepcopy(q)
        q2.append(i)
        que.append(q2)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

    @lru_cache(maxsize=None)
    def rec(n):
        if n < 0 or S[n] == '1':
            return None, INF
        elif n == 0:
            return None, 0
        min_i = None
        min_v = INF
        for i in range(max(n-M, 0), n):
            _, v = rec(i)
            if min_v > v:
                min_v = v
                min_i = i
        return min_i, min_v

    flag, _ = rec(N)
    if flag is None:
        print(-1)
    else:
        ans = []
        pos = N
        while pos != 0:
            prev_pos, _ = rec(pos)
            ans.append(pos - prev_pos)
            pos = prev_pos
        ans.reverse()
        print(*ans, sep=' ')



main()

Submission status: Time Limit Exceeded

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

    @lru_cache(maxsize=None)
    def rec(n):
        if n < 0 or S[n] == '1':
            return None, INF
        elif n == 0:
            return None, 0
        min_i = None
        min_v = INF
        for i in range(n-M, n):
            _, v = rec(i)
            if min_v > v:
                min_v = v
                min_i = i
        return min_i, min_v

    flag, _ = rec(N)
    if flag is None:
        print(-1)
    else:
        ans = []
        pos = N
        while pos != 0:
            prev_pos, _ = rec(pos)
            ans.append(pos - prev_pos)
            pos = prev_pos
        ans.reverse()
        print(*ans, sep=' ')



main()

Submission status: Time Limit Exceeded

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

def IsIt(): return map(lambda x: int(x), input().split())

n,m = IsIt()
mp = input()

p=dict()

from heapq import heappop, heappush
inf=float('inf')
d=[inf for i in range(n+1)] # 各ノードの最短距離
d[0]=0 # スタート地点の設定

prev=[None]*(n+1) # 各ノードの前ノード
q=[] # [(コスト，ノード番号)]
heappush(q,(d[0],0))
while q:
    # print(q,d,prev)
    du, u = heappop(q)
    if d[u]<du: continue # ノードにおけるコストが上書きされているため


    que = mp[u+1:u+m+1]
    #for v,weight in p.get(u,[]):
    for num,item in enumerate(que):
        if item == '1': continue
        v = u+num+1
        alt=du+1
        if d[v]>alt:
            d[v]=alt
            prev[v]=u
            heappush(q, (alt,v))

ans = ''

p = n

while prev[p]!=None:
    ans = str(p-prev[p])+' '+ans
    p = prev[p]




if ans == '':
    print(-1)
else:
    print(ans)