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/python3
# coding: utf-8

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

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

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

    p=[n-1]

    while prev[p[-1]]!=None:
        p.append(prev[p[-1]])

    
    # print('最短経路',*p[::-1])
    # print('最短距離',d)
    return p

    


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

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


que = mp[:m]
p=dict()

for num in range(n):

    if num >= n-m+1:
        item = ''
    else:
        item = mp[num+m]
    
    now = que[0]
    que = que[1:]+item

    if now == '1': continue

    new = []
    for num2, i_que in enumerate(que):
        if i_que == '1': continue
        new.append((num+num2+1,1))


    p[num] = new[:]

p = dijkstra(n+1,p)

ans = ''
prev = p[0]

for item in p[1:]:
    ans = str(prev-item)+' '+ans
    prev = item


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

Submission status: Time Limit Exceeded

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


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


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


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


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


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, S):
    def init():
        return [[INF, []] for _ in range(N+1)] 
    
    dp = init()
    dp[0] = [0, []]
    for i in range(N):
        tmp = deepcopy(dp)
        if S[i] == '1':
            continue
        for j in range(1, M+1):
            k = i + j
            if k > N:
                break
            if S[k] == '1':
                continue
            if dp[i][0] + 1 < dp[k][0]:
                c, s = dp[i]
                s = s[:]
                s.append(j)
                tmp[k] = [c + 1, s]
            elif dp[i][0] + 1 == dp[k][0]:
                c, s = dp[i]
                s1 = s[:]
                s2 = dp[k][1]
                for c1, c2 in zip(s1, s2):
                    if c1 > c2:
                        break
                else:
                    tmp[k] = [c + 1, s1]
        dp = tmp

    if dp[N][0] == INF:
        return -1
    return ' '.join(map(str, dp[N][1]))


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
s = str(input())
now = n
ans = ""
while now != 0:
    for num in range(min(m,now),0,-1):
        if s[now-num] == "0":
            now -= num
            ans=str(num)+" "+ans
            break
        else:
            if num == 1:
                print(-1)
                exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
s = str(input())
now = n
ans = []
while now != 0:
    for num in range(min(m,now),0,-1):
        if s[now-num] == "0":
            now -= num
            ans.insert(0,num)
            break
        else:
            if num == 1:
                print(-1)
                exit()
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
s=input()
a=[]
b=len(s)
c=0
d=n
e=0
while d>0:
  if d<=m:
    a.insert(0,d)
    d=0
  else:
    i=m
    while i>0:
      if s[d-i]=="1":
        i=i-1
      else:
        a.insert(0,i)
        d=d-i
        i=-1
    if i==0:
        e=1
        break
    else:
      continue
    break
if e==1:
  print(-1)
else:
  for i in range(len(a)):
    print(a[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
s=input()
a=[]
b=len(s)
c=0
d=n
e=0
while d>0:
  if d<=m:
    a.insert(0,d)
    d=0
  else:
    i=m
    while i>0:
      if s[d-i]=="1":
        i=i-1
      else:
        a.insert(0,i)
        d=d-i
        i=-1
    if i==0:
        e=1
        break
    else:
      continue
    break
if e==1:
  print(-1)
else:
  for i in range(len(a)):
    print(a[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
S,r,s=input(),[],N
exec("N,s,r=(s,max(0,s-M),r+([N-s]if N-s else[]))if S[s]=='0' else(N,s+1,r);"*2*N)
print(*[-1] if s else r[::-1])

Submission status: Time Limit Exceeded

Solution code:

### Use this space to try out ideas and free code ###
"""
Beginners Contests 146
F - Sugoroku
https://atcoder.jp/contests/abc146/tasks/abc146_f
"""
from collections import deque
import copy

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

# initialize
queue = deque([[0]])

distance_to_goal = N
while len(queue) > 0:
#    print("queue contents are {}".format(queue))
    here = queue.popleft()
 #   print("this queue is {}".format(here))
    # Get distance from start to here
    distance_from_start = sum(here)
    distance_to_goal = N - distance_from_start
#    print("distance_from_start:{0},N:{1},distance_to_goal:{2}".format(distance_from_start, N, distance_to_goal))

    if distance_to_goal < M:
        M = distance_to_goal

    for i in range(1, M + 1):
        tmp_here = copy.copy(here)
#        print("step count: {}".format(i))
#        print(S)
#        print("here step is {0}, char is {1} ".format(distance_from_start,S[distance_from_start]))
        
#        print("next step is {0} next char is {1}".format(str(distance_from_start + i),  S[distance_from_start + i]))
        if distance_from_start + i == N:
            # When next place to be Goal !!!
            tmp_here.append(i)
            tmp_here.pop(0)
            print(' '.join(map(str, tmp_here)))
            quit()
        # When place not to be game over 
        elif S[distance_from_start + i] != "1":
#            print("tmp_here:{0}, i:{1}".format(tmp_here, i))
            tmp_here.append(i)
#            print("append next queue:{0}".format(tmp_here))
            queue.append(tmp_here)
#        else:
#            print("next step will be game over X(")

print('-1')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

# stdin = open("testdata.txt", "r")

def input():
	return stdin.readline().strip()

from collections import deque

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

s = input()

def bfs(src):
	que = deque([[src, []]])
	visited = {src, }

	while que:
		u, path = que.popleft()
		if u == n:
			return path
		for i in range(1, m+1):
			next_pos = u + i
			if next_pos not in visited and next_pos <= n and s[next_pos]=='0':
				visited.add(next_pos)
				que.append((next_pos, path+[i]))
	return -1

ans = bfs(0)
if ans == -1:
	print(ans)
else:
	print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

s = input()

def bfs(src):
	que = deque([[src, []]])
	visited = {src, }

	while que:
		u, path = que.popleft()
		if u == n:
			return path
		for i in range(1, m+1):
			next_pos = u + i
			if next_pos not in visited and next_pos <= n and s[next_pos]=='0':
				visited.add(next_pos)
				que.append((next_pos, path+[i]))
	return -1

ans = bfs(0)
if ans == -1:
	print(ans)
else:
	print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
S=list(input())
S=S[::-1]
ans=[]
P=0
for i in range(1,N+1):
    if P==N:
        break
    for j in range(M+1):
        if P+(M-j)<=N and S[P+(M-j)]=="0":
            ans.append(M-j)
            P+=M-j
            break
ans=ans[::-1]
if 0 in ans:
    print(-1)
else:
    print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from collections import deque
import copy
import sys

def check(ps, l, S):
    p = sum(ps)
    if p+l == len(S)-1:
        return 1
    if int(S[p+l]) == 1:
        return -1
    return 0

queue = deque()

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

if '1'*M in S:
    print(-1)
    sys.exit()

for i in range(1, M+1):
    queue.appendleft([[0], i])

while True:
    nextqueue = deque()
    if len(queue) == 0:
        print(-1)
        sys.exit()
    while len(queue) != 0:
        ps, l = queue.pop()
        ps_ = copy.deepcopy(ps)
        ret = check(ps, l, S)
        if ret == 1:
            s = ''
            for p in ps[1:]:
                s += ' {}'.format(int(p))
            s += ' {}'.format(int(l))
            print(s[1:])
            sys.exit()
        elif ret == 0:
            ps_.append(l)
            for i in range(1, M+1):
                nextqueue.appendleft([ps_, i])
    queue = nextqueue

Submission status: Time Limit Exceeded

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

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in range(m, 0, -1):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(s))

Submission status: Time Limit Exceeded

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

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
        if i == n:
            cnt1_continuous = max(cnt1_continuous, cnt)
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(s))

Submission status: Time Limit Exceeded

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

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


def solve(t):
    if len(t) <= m + 1:
        return [len(t) - 1]
    for i in reversed(range(1, m + 1)):
        if t[len(t) - 1 - i] == '0':
            cand = solve(t[:-i])
            if len(cand) != 0:
                cand.append(i)
                return cand

    return []


cnt1_continuous = 0
cnt = 0
for i in range(n + 1):
    if s[i] == '1':
        cnt += 1
    else:
        cnt1_continuous = max(cnt1_continuous, cnt)
        cnt = 0

if cnt1_continuous >= m:
    print(-1)
else:
    print(*solve(s))

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

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


#solve
def solve():
    n, m = LI()
    s = S()
    d = Dijkstra(n + 1, 0, s, m)
    if d[-1] == inf:
        print(-1)
        return
    ans = []
    q = deque([n])
    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:
#!/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')

import time
def Dijkstra(num, start, s, m):
    b = time.time()
    dist = [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(1, m + 1):
            if s[i + k] == "1":
                continue
            dist[i + k] = a + 1
            x = i + k
            if i + k == num-1:
                return dist
    if x == -1:
        x = inf
    return dist


#solve
def solve():
    n, m = LI()
    s = S()
    d = Dijkstra(n + 1, 0, s, m)
    if d[-1] == inf:
        print(-1)
        return
    ans = []
    q = deque([n])
    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:
from collections import deque
INF = 10**18

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

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 = [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(1, m + 1):
            if s[i + k] == "1":
                continue
            dist[i + k] = a + 1
            x = i + k
            if i + k == num-1:
                return dist
    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:


N,M = map(int, input().split())
S = input()
inv_S =''
for i in range(N):
    inv_S = ''.join(list(reversed(S)))

ans = []
flag=0
while len(inv_S) != 1:
    max_len = min(M,len(inv_S)-1)
    for i in range(max_len,0,-1):
        if inv_S[i] == '0':
            ans = [i] + ans
            inv_S = inv_S[i:]
            break
        elif i==1:
            flag = -1
            break
    if flag == -1:
        break
    if inv_S =='0':
        break
if flag == -1:
    print(-1)
else:
    print(*ans)

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 = [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(1, m + 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:
from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq

dq = deque()
N,M = map(int, input().split())
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [[] for _ in range(N+1)]
dq.append(0)

for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    if c == "1":
        if i >= M:
            sxi = dq[0]
            if sxi == (i - M):
                dq.popleft()
        continue
    idx = dq[0]
    if dp1[idx] == INF:
        if i >= M:
            sxi = dq[0]
            if sxi == (i - M):
                dq.popleft()
        continue
    dp1[i] = dp1[idx] + 1
    dp2[i] = dp2[idx] + [i-idx]
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    print(" ".join(map(str, dp2[-1])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from collections import deque
import copy
import sys

def check(ps, l, S):
    p = sum(ps)
    if p+l == len(S)-1:
        return 1
    if int(S[p+l]) == 1:
        return -1
    return 0

queue = deque()

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

for i in range(1, M+1):
    queue.appendleft([[0], i])

while True:
    nextqueue = deque()
    if len(queue) == 0:
        print(-1)
        sys.exit()
    while len(queue) != 0:
        ps, l = queue.pop()
        ps_ = copy.deepcopy(ps)
        ret = check(ps, l, S)
        if ret == 1:
            s = ''
            for p in ps[1:]:
                s += ' {}'.format(int(p))
            s += ' {}'.format(int(l))
            print(s[1:])
            sys.exit()
        elif ret == 0:
            ps_.append(l)
            for i in range(1, M+1):
                nextqueue.appendleft([ps_, i])
    queue = nextqueue

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
INF = 10**18

def find_s(dq):
    minx = (-1, INF)
    for x in dq:
        if x[1] < minx[1]:
            minx = x
    return minx[0]

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append([i, x])
            break
        lxi = dq[-1][0]
        if x > dp1[lxi]:
            dq.append([i, dp1[i]])
            break
        dq.pop()
    return dq

dq = deque()
N,M = map(int, input().split())
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [[] for _ in range(N+1)]
dq.append([0, 0])

for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    if c == "1":
        if i >= M:
            sxi = dq[0][0]
            if sxi == (i - M):
                dq.popleft()
        continue
    idx, vx = dq[0]
    if dp1[idx] == INF:
        if i >= M:
            sxi = dq[0][0]
            if sxi == (i - M):
                dq.popleft()
        continue
    dp1[i] = dp1[idx] + 1
    dp2[i] = dp2[idx] + [i-idx]
    if i >= M:
        sxi = dq[0][0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    print(" ".join(map(str, dp2[-1])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree, index, op2 = self.op, self.tree, self.index, self.op2
        while i > 1:
            i >>= 1
            v1, v2 = tree[i<<1], tree[(i<<1)+1]
            tree[i] = op(v1, v2)
            index[i] = index[(i<<1) + op2(v1, v2)]


N, M = map(int, input().split())
S = list(map(int, input()))
dp = [10 ** 9] * (N + 1)
seg = SegTreeIndex(dp)
from_ = [-10000000] * (N + 1)
seg.set_value(0, 0)
for i, c in enumerate(S[1:], 1):
    if c == 1:
        continue
    v, idx = seg.get_value(max(i - M, 0), i)
    if v == 1000000000:
        print(-1)
        exit()
    from_[i] = idx
    seg.set_value(i, v + 1)
n = seg.tree[N + seg.elem_size]
# print(seg.tree[seg.elem_size:seg.elem_size+N+1])
# print(from_)

Ans = []
v = N
while v != 0:
    v_ = from_[v]
    Ans.append(v - v_)
    v = v_
Ans.reverse()
print(" ".join(map(str, Ans)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def copy(a):
    return ccc.deepcopy(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, a)
print(" ".join([str(i) for i in a[1]]))