Problem: 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.

Submission attempts (in order):
N, M = map(int, input().split())
S = input()


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)

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

    
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        R = min(R, self.n + 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



RMQ = RangeMinimumQuery(N + 1)
RMQ.update(N, 0)
for i in range(N - 1, -1, -1):
    if S[i] == '1':
        continue

    
    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)


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


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)

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

    
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        R = min(R, len(self.segtree))
        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



RMQ = RangeMinimumQuery(N + 1)
RMQ.update(N, 0)
for i in range(N - 1, -1, -1):
    if S[i] == '1':
        continue

    
    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)


Verdicts: Wrong Answer

Accepted