Problem p02852 (python)

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


# 後ろから貪欲
ans = []
position = N
while position > 0:
    for move in range(M, 0, -1):
        if position - move < 0:
            continue

        if S[position - move] == '1':
            continue

        ans.append(move)
        position -= move
        break
    else:
        print(-1)
        exit()

print(*ans[::-1])

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = input()

# dp[i] := ゴールから最短何手でマスiにたどり着けるか
dp = [float('inf')] * (N + 1)
dp[-1] = 0


class RangeMinimumQuery:
    def __init__(self, n, inf=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INF = inf
        self.segtree = [self.INF] * (2 * self.n)

    # i番目の値(0-indexed)をxに変更
    def update(self, i, x):
        i += self.n
        self.segtree[i] = x
        while i > 0:
            i //= 2
            self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

    # [l, r)のmin
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        R = min(R, len(self.segtree) + 1)
        s = self.INF
        while L < R:
            if L & 1:
                s = min(s, self.segtree[L])
                L += 1

            if R & 1:
                s = min(s, self.segtree[R - 1])
                R -= 1

            L >>= 1
            R >>= 1

        return s


# セグメント木でdpテーブルを高速に埋める
RMQ = RangeMinimumQuery(N + 1)
RMQ.update(N, 0)
for i in range(N - 1, -1, -1):
    if S[i] == '1':
        continue

    # RMQ.query(l, r) := [l, r)の最小値
    dp[i] = RMQ.query(i, i + M + 1) + 1
    RMQ.update(i, dp[i])


ans = []
position = 0
while position < N:
    for move in range(1, M + 1):
        if position + move > N:
            continue

        if S[position + move] == '1':
            continue

        # 最短手数にならない
        if dp[position + move] == dp[position]:
            continue

        ans.append(move)
        position += move
        break

    else:
        print(-1)
        exit()

print(*ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = list(input())

n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


i = len(move) - 1
move.sort()
n = N
ans = []
while move:
    if S[n - move[i]] != '1':
        ans.append(move[i])
        n -= move[i]
        del move[i]
        i = len(move) - 1
    else:
        i -= 1

print(*ans[::-1])

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = list(input())

n = 0
next_n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


print(1 / 0)
# i = len(move) - 1
# move.sort(reverse=True)
# n = 0
# ans = []
# while move:
#     if S[n + move[i]] != '1':
#         ans.append(move[i])
#         n += move[i]
#         del move[i]
#         i = len(move) - 1
#     else:
#         i -= 1
# 
# print(*ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = list(input())

n = 0
next_n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


i = len(move) - 1
move.sort(reverse=True)
n = 0
ans = []
while move:
    if S[n + move[i]] != '1':
        ans.append(move[i])
        n += move[i]
        del move[i]
        i = len(move) - 1
    else:
        i -= 1

print(*ans)