Problem:


Score : 600 points

Problem Statement

Takahashi is playing a board game called Sugoroku.

On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.

The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.

Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.

Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.

Constraints

1 \leq N \leq 10^5

1 \leq M \leq 10^5

|S| = N + 1

S consists of 0 and 1.

S[0] = 0

S[N] = 0

Input

Input is given from Standard Input in the following format:

N M
S

Output

If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.

If Takahashi cannot win the game, print -1.

Sample Input 1

9 3
0001000100

Sample Output 1

1 3 2 3

If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.

Sample Input 2

5 4
011110

Sample Output 2

-1

Takahashi cannot reach Square 5.

Sample Input 3

6 6
0101010

Sample Output 3

6



Sample input:
9 3
0001000100


Sample output:
1 3 2 3

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        #self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:
    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.size=n
        self.ide_ele=ide
        self.num=1<<(self.size-1).bit_length()
        self.table=[self.ide_ele]*2*self.num
        self.index=[0]*2*self.num
        self.lazy=[self.ide_ele]*2*self.num
        self.func=function
        #set_val
        if not hasattr(init_val,"__iter__"):
            init_val=[init_val]*self.size
        for i,val in enumerate(init_val):
            self.table[i+self.num-1]=val
            self.index[i+self.num-1]=i
        #build
        for i in range(self.num-2,-1,-1):
            self.table[i]=self.func(self.table[2*i+1],self.table[2*i+2])
            if self.table[i]==self.table[i*2+1]:
                self.index[i]=self.index[i*2+1]
            else:
                self.index[i]=self.index[i*2+2]
        
    def update(self,k,x):
        k+=self.num-1
        self.table[k]=x
        while k:
            k=(k-1)//2
            res=self.func(self.table[k*2+1],self.table[k*2+2])
            self.table[k]=res
            if res==self.table[k*2+1]:
                self.index[k]=self.index[k*2+1]
            else:
                self.index[k]=self.index[k*2+2]
        
    def evaluate(k,l,r): #遅延評価処理
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
    
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
            if q&1==1:
                res=self.func(res,self.table[q])
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
        return res
    
    def query_id(self,p,q):
        if q<=p:
            return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        res=self.ide_ele
        idx=p
        while q-p>1:
            if p&1==0:
                res=self.func(res,self.table[p])
                if res==self.table[p]:
                    idx=self.index[p]
            if q&1==1:
                res=self.func(res,self.table[q])
                if res==self.table[q]:
                    idx=self.index[q]
                q-=1
            p=p>>1
            q=(q-1)>>1
        if p==q:
            res=self.func(res,self.table[p])
            if res==self.table[p]:
                idx=self.index[p]
        else:
            res=self.func(self.func(res,self.table[p]),self.table[q])
            if res==self.table[p]:
                idx=self.index[p]
            elif res==self.table[q]:
                idx=self.index[q]
        return idx


    def __str__(self):
        # 生配列を表示
        rt=self.table[self.num-1:self.num-1+self.size]
        return str(rt)

show_flg=False
show_flg=True
ans=0

n,m=LI()
s=[int(i) for i in input()]
 
def dp(b,m): # N log (N)
    N=len(b)-1
    n=N+1
    sg=SegTree(n,inf,min,inf)
 
    sg.update(0,0)
 
    dp=[0]+[inf]*(N)
    for i in range(N):
        if b[i+1]==1:
            continue
        dp[i+1]=sg.query(max(i-m+1,0),i+1)+1
        sg.update(i+1,dp[i+1])

    return dp
 
dp1=dp(s,m)
step=dp1[n]
if step==inf:
    print(-1)
    exit()
 
dp2=dp(s[::-1],m)[::-1]
 

move=[0]
ans=[]
j=1
for i in range(step,0,-1): # N
    while j<=n and dp2[j]!=i-1:
        j+=1
    move.append(j)
 
for i in range(len(move)-1):
    ans.append(move[i+1]-move[i])
print(*ans)
exit()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=list(map(int,list(input())))
ans=[]
i=n
while i>0:
  j=max(0,m-i)
  while s[i-(m-j)]!=0:
    j+=1
    if j==m:
      print(-1)
      exit(0)
  ans.append(m-j)
  i-=(m-j)
ans.reverse()
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5 + 1
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()
    S = SI()
    N0 = 2 ** N.bit_length()
    st = [INF] * (2*N0)

    def update(i,x):
        i += N0-1
        st[i] = x
        while i > 0:
            i = (i-1) // 2
            st[i] = min(st[i*2+1], st[i*2+2])

    def query(l,r):
        L = l+N0; R = r+N0
        ret = INF
        while L < R:
            if L % 2:
                ret = min(ret,st[L-1])
                L += 1
            if R % 2:
                R -= 1
                ret = min(ret,st[R-1])
            L //= 2; R //= 2
        return ret

    update(0,0)

    for i in range(1,N+1):
        if S[i] == '1': continue
        else:
            if i <= M:
                update(i,1)
            else:
                x = query(i-M,i)
                update(i,x+1)
    if st[N+N0-1] >= INF:
        print(-1)
    else:
        ans = []
        f = N
        last_i = N
        s = st[N+N0-1]
        d = 1
        cnt = 0
        for i in range(N-1,-1,-1):
            cnt += 1
            if st[i+N0-1] == s-1:
                d = f - i
                last_i = i
            if cnt == M:
                ans.append(d)
                f = last_i
                s -= 1
                cnt = f - i
        if f > 0:
            ans.append(f)
        print(*reversed(ans),sep=' ')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()[::-1]
ans=[]
now=0
while(now<n):
  t=1
  for i in reversed(range(1,m+1)):
    if now+i>n or s[now+i]=='1':
        continue
    now=now+i
    ans.append(i)
    t=0
    break
  if t:
    print(-1)
    exit()
ans.reverse()
print(*ans,sep=' ')

Submission status: Accepted

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

p = N
ans = []
ans_ok = True
while True:
    if p <= M:
        ans.append(p)
        p -= p
        break
    check = False
    for i in range(M, 0, -1):
        if S[p-i] == '0':
            check = True
            ans.append(i)
            p -= i
            break
    if not check:
        ans_ok = False
        break
if ans_ok:
    print(' '.join(map(str, ans[::-1])))
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    elif c < m-1:
        c += 1
    else:
        break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    else:
        c += 1
        if c >= m:
            break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
out_s='1'*(m)
if out_s in s:
    print(-1)
    exit()
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: Accepted

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

import math
import bisect

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

L = [(1<<i) -1 for i in range(1,M+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(bisect.bisect_left(L,b)+1)

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

Submission status: Accepted

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

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

cnt=0
from collections import defaultdict
d = defaultdict(int)
d[cnt]=n
for i in reversed(range(len(s))):
    if d[cnt] - i > m:
        cnt+=1
    if s[i]=="0":
        d[cnt+1]=i
d[cnt+1]=0

ans=[]
for i in reversed(range(len(d)-1)):
    ans.append(d[i] - d[i+1])
print(*ans,sep=" ")

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
S=input()
lst=[]
koma=N
rs=0
ME=0
pn=0
while koma>0 and pn==0:
 rs+=1
 if int(S[koma-rs])==0:
  ME=rs
 if koma-rs==0 or rs==M:
  lst.append(ME)
  if ME==0:
   pn+=1
  koma-=ME
  rs=rs-ME
  ME=0
if pn>0:
 print(-1)
else:
 lst.reverse()
 print(*lst)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
S=list(input()) #S[0]....S[N]
flag=1
done=0
piv=N
ans=deque()
while flag==1:
    done=0
    for i in range(max(0,piv-M),piv):
        if S[i]=="0":
            ans.appendleft(piv-i)
            piv=i
            done=1
            break
    if piv==0:
        break
    if done==0:
        flag=0
        break
    #print(piv,ans)
#print(flag)
if flag==1:
    print(*ans)
else:
    print("-1")

Submission status: Accepted

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

S.reverse()

#後ろから貪欲に

a = 0  #合計何マス進んだか
A = []  #何マスずつ進んでいるか

while a < N:
    if N-a <= M:
        A.append(N-a)
        a = N
    else:
        for i in range(M,0,-1):
            if S[a+i] == 0:
                A.append(i)
                a += i
                break
        else:
            print(-1)
            exit()

A.reverse()
print(*A)

Submission status: Accepted

Solution code:



N,M = map(int, input().split())
S = input()
cnt = 0
for s in S:
    if s == "0":
        cnt = 0
    else:
        cnt += 1
        if cnt >= M:
            print(-1)
            exit()


"""
辞書順最小
・より少ない回数でゴール
・同じ回数なら、低い数字ほど左にくる

N歩先がゴール　→　出目の合計がNになったらOK
iマス目を踏むとゲームオーバー　→　途中で出目の合計がiになるとアウト

ただ、辞書順が厄介
N=4, 00000があったとして、M=3の場合、3->1より1->3の方が辞書順で若い。なので、スタート地点から貪欲に進めるだけ進む、は条件を満たさない。
→　ゴールからスタートに帰る。移動方法は貪欲にする。
"""

ans = []
rS = S[::-1]
l = 0
r = 1
while l < N:
    r = l + 1
    stoppable = l
    while r - l <= M and r <= N:
        if rS[r] == "0":
            stoppable = r
        r += 1
    
    ans.append(stoppable - l)

    l = stoppable

print(*ans[::-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = list(map(int, reversed(input())))
now = 0
ans = []
while now + M < N:
    last = now
    now += M
    while S[now]:
        now -= 1
    if last == now:
        print(-1)
        break
    ans.append(now - last)
else:
    print(*reversed(ans + [N - now]))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
s = input()
s = s[::-1]
ans = list()
goal = False
now = 0
while not goal:
    for adv in reversed(range(1,m+1)):
        if now + adv >= n:
            ans.append(n-now)
            goal = True
            break
        elif s[now+adv] == '0':
            ans.append(adv)
            now += adv
            break
    else:
        print(-1)
        break

if goal:
    print(*ans[::-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# F

from collections import deque
import sys

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

d = deque()
res = []
prev_idx = 0

while True:
    found = False
    idx = prev_idx
    for m in range(M):
        idx += 1
        if S[idx] == '0':
            # print(idx)
            d.append(m+1)
            found = True
            prev_idx = idx
        if idx == N:
            res.append(str(d.pop()))
            print(' '.join(res[::-1]))
            sys.exit()
    if not found:
        print(-1)
        sys.exit()
    res.append(str(d.pop()))

Submission status: Accepted

Solution code:
import sys
N, M = map(int,input().split())
S = input()
S = S[::-1]
i = 0
ans = []
while i < N:
    flag = 0
    for j in range(M,0,-1):
        if i + j <= N and S[i + j] == '0':
            i += j
            flag = 1
            ans.append(j)
            break
    if flag:
        continue
    print(-1)
    sys.exit()
ans.reverse()
print(*ans)

Submission status: Accepted

Solution code:
#F sugoroku
#貪欲にNからM以下の範囲で戻れるだけ戻ることにする
safe=[]
n,m=map(int,input().split())
field=list(input())
for i in range(n+1):
    if field[i]=="0":
        safe.append(i)
start=n

import bisect

deque=[]
flag=True
while start>0:
    if start>=m:
        index=bisect.bisect_left(safe,start-m)
        if safe[index]!=start:
            deque.append(start-safe[index])
            start=safe[index]           

        elif safe[index]==start:
            flag=False
            start=0              
    else:
        deque.append(start)
        start=0
if flag:
    deque=deque[::-1]
    print(*deque)
else:
    print(-1)

Submission status: Accepted

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    s = input()    # 長さは n + 1
    minimum_turn = 1
    ans = []
    prev = n
    current = prev - m
    while current > 0:
        for i in range(current, prev):
            if s[i] == '0':
                ans.append(m - (i - current))
                prev = i
                current = i - m
                minimum_turn += 1    # 途中のマスで中継を行った
                break
        else:
            print(-1)
            exit()
    
    # minimum_turn でたどり着くパスのうち辞書順最小を求める
    ans.append(n - sum(ans))
    ans.reverse()
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    s = input().rstrip()
    s = s[::-1]
    # 右から0, 1, 2...とした時のセーフな位置
    safe = []
    for i in range(n+1):
        if s[i] == '0':
            safe.append(i)
    res = []

    pos = 0
    while pos < n:
        pre = pos
        pos += m
        if pos >= n:
            res.append(str(n-pre))
            break
        idx = bisect_left(safe, pos)
        if safe[idx] > pos:
            pos = safe[idx-1]
        if pre == pos:
            print(-1)
            exit()
        res.append(str(pos-pre))
    print(*res[::-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

s = input()

ans = []
p = n

flag = 1
while flag:
    for j in range(m,0,-1):
        if p-j<=0:
            ans.append(p)
            flag = 0
            break
        elif s[p-j]=='0':
            ans.append(j)
            p-=j
            break
        elif j == 1:
            ans.append(-1)
            flag = 0
            break

print(' '.join(map(str,reversed(ans))) if ans[-1]!=-1 else -1)

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=list(input())
    S2=S[::-1]
    
    now=0
    ans=[]
    while now!=N:
        nxt=now+M
        if nxt>N:
            nxt=N
        while S2[nxt]=="1":
            nxt-=1
        if now==nxt:
            ans=[-1]
            break
        ans.append(nxt-now)
        now=nxt
        
    print(' '.join(map(str, ans[::-1])))
    
main()

Submission status: Accepted

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

from collections import deque

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
s = list(ns())
s = s[::-1] #n+1

ans = []
i = 0
while True:
    j = i+m if i+m < n else n
    for k in reversed(range(i+1,j+1)):
        if s[k] == '0':
            ans.append(k-i)
            i = k
            break
    else:
        print(-1)
        exit()
    if i == n:
        break

print(*ans[::-1],sep=' ')

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, M = read_values()
    S = input().strip()[::-1]
    P = []
    t = 0
    tmp = 1
    for s in S[1:]:
        if s == "0":
            t = tmp
        
        tmp += 1
        if tmp > M:
            if t == 0:
                print(-1)
                return

            P.append(str(t))
            tmp -= t 
            t = 0
    
    if t != 0:
        P.append(str(t))
    print(" ".join(P[::-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import *
n,m = map(int,input().split())
S = input()
ok = []
for i,s in enumerate(S[::-1]):
    if s == '0':
        ok.append(i)

now = 0
ans = []
while now != n:
    nxt = ok[bisect_right(ok, now + m) - 1]
    if nxt == now:
        ans = [str(-1)]
        break
    else:
        ans.append(str(nxt - now))
        now = nxt
print(' '.join(ans[::-1]))