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: Wrong Answer

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

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


class SegmentTree:

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

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

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

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

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

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

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

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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


class SegmentTree:

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

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

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

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

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

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

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

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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
S = input()[::-1]
ans = ''
i = 0
while i < N - M:
    found = False
    for j in range(M, 0, -1):
        if S[i + j] == '0':
            ans += str(j)
            i += j
            found = True
            break
    if not found:
        print(-1)
        sys.exit()
ans += str(N-i)
print(' '.join(ans[::-1]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()
cnt=0
f=False
for i in s:
  if int(i):
    cnt+=1
    if cnt==m:
      f=True
      break
  else:
    cnt=0
if f:
  print(-1)
else:
  dl=[None for i in range(n+1)]
  dp=[[] for i in range(n+1)]
  point=[i for i in range(n+1)]
  point2=[i for i in range(n+1)]
  temp=n
  sr=[]
  for i in range(1,1+min(m,n)):
    if s[n-i]=="0":
      dl[n-i]=1
      dp[n-i]=[i]
      temp=n-i
      for j in sr:
        point2[j]=n-i
      sr=[]
    else:
      point[n-i]=temp
      sr.append(n-i)
  for i in range(1+min(m,n),n+1):
    if s[n-i]=="1":
      point[n-i]=temp
      sr.append(n-i)
    else:
      for j in sr:
        point2[j]=n-i
      sr=[]
      temp=n-i
      l,r=n-i,point2[n-i+m]
      while True:
        t=point[(l+r+1)//2]
        if r==t:
          break
        elif dl[t]==dl[r]:
          r=t
        else:
          l=t
      dl[n-i]=dl[r]+1
      dp[n-i]=dp[r]+[r-n+i]
  
  r=""
  for i in dp[0][::-1]:
    r+=str(i)+" "
  print(r[:-1])

Submission status: Wrong Answer

Solution code:
def coin(larger=False, single=False):
    """
    ナップサックに入れる重さが W 丁度になる時の価値の最小値
    :param larger: False = (重さ = W)の時の最小価値
                   True  = (重さ =< W)の時の最小価値
    :param single: False = 重複あり

    dp[weight <= W+1] = 重さを固定した時の最小価値
    dp[W+1] = 重さがWより大きい時の最小価値
    """
    W2 = N + 1              # dp[W+1] に W より大きい時の全ての場合の情報を持たせる
    dp_max = float("inf")   # 総和価値の最大値
    dp = [dp_max] * (W2 + 1)
    dp[0] = 0               # 重さ 0 の時は価値 0


    for item in range(M):
        if single:
            S = range(W2, weight_list[item] - 1, -1)
        else:
            S = range(W2)
        for weight in S:
            if weight + weight_list[item] >= W2 or data[weight + weight_list[item]] == "1":
                continue
            A, B = dp[weight + weight_list[item]], dp[weight] + cost_list[item]
            if A < B:
                dp[weight + weight_list[item]] = A
            else:

                dp[weight + weight_list[item]] = B
                parent[weight + weight_list[item]] = weight
    if larger:
        return min(dp[w] for w in range(N, W2 + 1))
    else:
        return dp[N]

#######################################################################################################
import sys
input = sys.stdin.readline

def max2(x, y): return x if x > y else y
def min2(x, y): return x if x < y else y

N, M = map(int, input().split())                                # N: 品物の種類 W: 重量制限
data = input().rstrip()

cost_list = [1] * M
weight_list = []
for i in range(1,M+1):
    """ cost と weight が逆転して入力されている場合有り """
    weight_list.append(i)
parent = [-1]*(N+2)
if coin(larger=False, single=False) == float("inf"):
    print(-1)
    exit()
p = N
res = []
while parent[p] != -1:
    q = parent[p]
    res.append(p-q)
    p = q
res.reverse()
print(*res)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

def segfunc(x, y):
    return min(x, y)

ide_ele = float('inf')

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

# 最短手数k回でクリアできるとすると、
# 1 ~ M　の内１つをk回選んで合計をNにする
N, M = getNM()
S = input()
trap = set()
for i in range(len(S)):
    if S[i] == '1':
        trap.add(i)

# 案1 dpを使う
# dp[i]: iマスに止まる時の最短手順
# dp[i]の時 dp[i + 1] ~ dp[i + M]についてmin(dp[i], dp[i + j] + 1)を見ていく
# 決まったらdpを前から見ていき最短手順がdp[i] - 1になるものを探す（辞書順）
# → M <= 10 ** 5より多分無理

# セグ木使えばいける？
# dp[i]についてdp[i - M] ~ dp[i - 1]の最小値 + 1

dp = [float('inf')] * (N + 1)
dp[0] = 0
seg = SegTree([float('inf')] * (N + 1), segfunc, ide_ele)
seg.update(0, 0)

for i in range(1, N + 1):
    if i in trap:
        continue
    min_t = seg.query(max(0, i - M), i)
    seg.update(i, min_t + 1)
    dp[i] = min_t + 1

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

now = 0
ans = []
# dp[i]の1, 2, 3, 4...について
# 各数字の先頭のものがある場所へ行くように出目を調整する
for i in range(1, N + 1):
    if dp[i] == dp[now] + 1:
        ans.append(i - now)
        now = i

# 最後（goalする時）だけは末尾に行くように
ans[-1] += N - now
print(*ans)

Submission status: Wrong Answer

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


def answer():
    a = n
    pips = []
    while a > 0:
        step = False
        for pip in range(m, 0, -1):
            if a - pip < 0:
                continue
            if s[a - pip] == "0":
                a -= pip
                pips.append(pip)
                step = True
        if not step:
            return -1

    return reversed(pips)


a = answer()
if a == -1:
    print(a)
else:
    print(" ".join(str(i) for i in a))

Submission status: Wrong Answer

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

i=0
while i<n:
    j=i
    cur=-1
    while j<n and j+1-i<=m:
        j+=1
        if s[j]=='0':
            cur=j
    if cur<0:
        print(-1)
        exit(0)

    ans+=str(cur-i)+' '
    i=cur

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()
from itertools import groupby
gr=groupby(s)
l=[]
for k,g in gr:
  l.append((k,len(list(g))))

for ll in l:
  k,v=ll
  if k=="1" and v>=m:
    print(-1)
    exit(0)
cur=0
path=[]
while cur<n:
  if s[min(cur+m,n)]=="1":
    if cur+m>=n-m:
      for i in range(1,m):
        if cur+i==n-m:
          if s[min(cur+i,n)]=="0":
            cur+=i
            path.append(i)
            break
    else:
      for i in range(1,m):
        if s[min(cur+i,n)]=="0":
          cur+=i
          path.append(i)
          break
  else:
    if cur+m>=n-m:
      for i in range(1,m+1):
        if cur+i==n-m:
          if s[min(cur+i,n)]=="0":
            cur+=i
            path.append(i)
            break
    cur+=m
    path.append(m)
print(*path)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=input()
from itertools import groupby
gr=groupby(s)
l=[]
for k,g in gr:
  l.append((k,len(list(g))))

for ll in l:
  k,v=ll
  if k=="1" and v>=m:
    print(-1)
    exit(0)
cur=0
path=[]
while cur<n:
  if s[min(cur+m,n)]=="1":
    if cur+m>=n-m:
      for i in range(1,m):
        if cur+i==n-m:
          if s[min(cur+i,n)]=="0":
            cur+=i
            path.append(i)
            break
    else:
      for i in range(1,m):
        if s[min(cur+i,n)]=="0":
          cur+=i
          path.append(i)
          break
  else:
    cur+=m
    path.append(m)
print(*path)

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())
S = readline().decode().rstrip()
arr = []
max_dist = 0
while True:
  tmp_max = max_dist
  for m in range(M,0,-1):
      tmp = tmp_max+m
      if tmp > N:
          continue
      if S[tmp] == '0':
          max_dist = tmp
          arr.append(m)
          break
      if m == 1:
        print(-1)
        sys.exit()
  if max_dist == N:
      break
print(*arr)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_f
# F - Sugoroku

def search(a,x,ans):
    if x==0:
        #ans_list.append(ans)
        final=ans[::-1]
        ret=[]
        for i in range(1,maxi+1):
            ret.append(final[i]-final[i-1])
        print(*ret)
        sys.exit()
    else:
        target=L[x-1]
        for p in target:
            if a-p<=M:
                ret=search(p,x-1,ans+[p])                

import sys
N,M = map(int,input().split())
S=list(input())
#print(S)

dp=[float("inf")]*(N+1)
dp[0]=0

for i in range(1,N+1):
    if S[i]=="1":
        pass
    else:
        for j in range(1,M+1):
            if i>=j:
                if S[i-j]=="0":
                    tmp= dp[i-j]+1
                    dp[i]=min(tmp,dp[-1])
#print(dp)
if dp[-1]==float("inf"):
    print(-1)
else:
    maxi=dp[-1]
    L=[ [] for _ in range(maxi+1)]
    for i,num in enumerate(dp):
        if num!=float("inf"):
            L[num].append(i)

    t = maxi
    ans_list=[N]
    print(L)
    print(t,ans_list)
   
    for i in range(maxi):
        for num in L[t-1]:
            if 1<= ans_list[-1] - num <= M:
                ans_list.append(num)
                t -=1
                break
    print(ans_list)
    fin=ans_list[::-1]
    final_ans=[]
    for j in range(1,maxi+1):
        final_ans.append(fin[j]-fin[j-1])
    print(*final_ans)

Submission status: Wrong Answer

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

tmp = 0
sum1 = 0
ans = ''

while tmp < n:
    for i in range(m, 0, -1):
        flag = False
        if tmp + i <= n:
            if s[tmp+i] == '0':
                tmp += i
                flag = True
                sum1 += 1
                ans += str(i)
                break
    if not flag:
        print(-1)
        exit()

for i in ans[::-1]:
    print(i, end = ' ')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n, m = list(map(int, input().split(' ')))
routes = [int(i) for i in input()]
ans = []
min_length = 9999999999999
def f(current, history):
    global ans
    global min_length
    # todo: 多分TLEなのでここで history ごとメモってしまう？
    
    if current >= n:
        if current == n:
            if len(history) < min_length:
                ans = history[:]
                min_length = len(ans)
            if len(history) == min_length:
                if ''.join([str(z) for z in ans]) > ''.join(str(z) for z in history):
                    ans = history[:]
        return -1
    for i in range(1, m+1):
        if current + i >= len(routes) or routes[current + i]:
            continue
        f(current + i, history + [i])
f(0, [])

print(ans if ans != [] else -1)

Submission status: Wrong Answer

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




def main():
    N ,M = map(int,input().split())
    S = list(str(input()))
    p =N
    act = 0
    ans =[]
    while True:
        if p <=M:
            ans.append(p)
            break

        for i in range(M,0,-1):
            if S[p - i] =="1":
                continue
            else:
                p = p-i
                act +=1
                ans.append(i)
                break
        if i ==1:
            print(-1)
            exit()



    for l in reversed(ans):
        print(l,sep="",end=" ")









if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

cnt = 0
pos = 0
tmp = 0
lst = []
while pos != n:
    pos += 1
    cnt += 1
    if cnt == m:
        if sugoroku[pos] == "0":
            lst.append(cnt)
            cnt = 0
        else:
            if tmp == 0:
                print(-1)
                exit()
            lst.append(tmp)
            cnt -= tmp
            tmp = 0
    else:
        if sugoroku[pos] == "0":
            tmp = cnt
if cnt != 0:
    lst.append(cnt)
for num in lst:
    print(num)

Submission status: Wrong Answer

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

if M >= N:
    print(N)
    exit()

p = -1
for i in reversed(range(1,M+1)):
    if S[i] == "0":
        p = i
        break

if p == -1:
    print(-1)
    exit()

ps = [p]
for _ in range(N//M):
    tmp = -1
    for i in reversed(range(ps[-1]+1,ps[-1]+M+1)):
        try:
            if S[i] == "0" or i == N:
                ps.append(i)
                tmp = i
                break
        except:
            pass
    if tmp == -1:
        print(-1)
        exit()

pp = ([ps[i+1]-ps[i] for i in range(len(ps)-1)])[::-1] + [ps[0]]
print(*pp)

Submission status: Wrong Answer

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

if M >= N:
    print(N)
    exit()

p = -1
for i in reversed(range(1,M+1)):
    if S[i] == "0":
        p = i
        break

if p == -1:
    print(-1)
    exit()
print(p)
ps = [p]
for _ in range(N//M):
    tmp = -1
    for i in reversed(range(ps[-1]+1,ps[-1]+M+1)):
        try:
            if S[i] == "0" or i == N:
                ps.append(i)
                tmp = i
                break
        except:
            pass
    if tmp == -1:
        print(-1)
        exit()

pp = ([ps[i+1]-ps[i] for i in range(len(ps)-1)])[::-1] + [ps[0]]
print(*pp)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = input()
prev = N
pos = N
ans = []
while pos > 0:
    for i in range(M, 0, -1):
        if pos - i >= 0 and S[pos - i] == '0':
            ans.append(i)
            pos -= i
    if pos == prev:
        ans = [-1]
        break
    prev = pos
print(*ans[::-1])

Submission status: Wrong Answer

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

if M >= N:
    print(N)
    exit()

p = -1
for i in reversed(range(1,M+1)):
    if S[i] == "0":
        p = i
        break

if p == -1:
    print(-1)
    exit()
print(p)
ps = [p]
for _ in range(N//M):
    tmp = -1
    for i in reversed(range(ps[-1]+1,ps[-1]+M+1)):
        try:
            if S[i] == "0":
                ps.append(i)
                tmp = i
                break
        except:
            pass
    if tmp == -1:
        print(-1)
        exit()
pp = [ps[i+1]-ps[i] for i in range(len(ps)-1)]
pp = pp[::-1]
print(*pp,end=" ")
print(ps[0])

Submission status: Wrong Answer

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 = 0
        if f > 0:
            ans.append(f)
        print(*reversed(ans),sep=' ')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 = 0
        s = 1
        d = 1
        last_i = 0
        for i in range(1,N+1):
            if st[i+N0-1] == s+1:
                ans.append(d)
                f = last_i
                s += 1
            if st[i+N0-1] == s:
                d = i - f
                last_i = i
        ans.append(N-f)
        print(*ans,sep=' ')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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):
  b = ((b<<1) + S[i]) & mask
  max_n.append(len(bin(mask-b))-2)

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

Submission status: Wrong Answer

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 = []
print(max_n[-10:])
while now != 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

Submission status: Wrong Answer

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 = [S[i] for i in range(N)]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
#############
# Libraries #
#############
 
import sys
input = sys.stdin.readline
 
import math
 
N,M = map(int,input().split())
S = input()
 
if "1"*M in S:
  print(-1)
  exit()

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math

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

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

max_n = [0 for i in range(N+1)]

for i in range(1,N+1):
  s = S[max(0,i-M):i]
  l = len(s)
  mask = (1<<l) -1
  b = (~int(s, 2)) & mask
  max_n[i] = math.floor(math.log(b)/math.log(2))+1

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math

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

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

max_n = [0 for i in range(N+1)]

for i in range(1,N+1):
  s = S[max(0,i-M):i]
  l = len(s)
  mask = (1<<l) -1
  b = (~int(s, 2)) & mask