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: Runtime Error

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

N += 1
# Max size of tree  
tree = [0] * (2 * N);  
n = N
# function to build the tree  
def build() : 
  
    # insert leaf nodes in tree  
    for i in range(N) :  
        tree[n + i] = (float('inf'), float('inf'));  
      
    # build the tree by calculating parents  
    for i in range(n - 1, 0, -1) :  
        tree[i] = min(tree[i << 1], tree[i << 1 | 1])
  
# function to update a tree node  
def updateTreeNode(p, value) :  
      
    # set value at position p  
    tree[p + n] = (value, p);  
    p = p + n;  
      
    # move upward and update parents  
    i = p; 
      
    while i > 1 : 
          
        tree[i >> 1] = min(tree[i], tree[i ^ 1]);  
        i >>= 1;  
  
# function to get sum on interval [l, r)  
def query(l, r) :  
  
    res = (float('inf'), float('inf'));  
      
    # loop to find the sum in the range  
    l += n; 
    r += n; 
      
    while l < r : 
      
        if (l & 1) : 
            res = min(res, tree[l]);  
            l += 1
      
        if (r & 1) : 
            r -= 1; 
            res = min(res, tree[r]);  
              
        l >>= 1; 
        r >>= 1
      
    return res;

par = [None for i in range(N)]
build()
updateTreeNode(0, 0)
for i in range(1, N):
    if s[i] == "1": continue
    r = query(max(0, i - M), i)
    par[i] = r[1]
    updateTreeNode(i, r[0]+1)
    # updateTreeNode(i, query(max(0, i - M), i))
    
    # for k in range(1, M+1):
    #     if i - k < 0: break
    #     dp[i] = min(dp[i], (dp[i-k][0], (i - k)))



moves = []
cur = N - 1
if par[cur] == float('inf'):
    print(-1)
    quit()
while par[cur] != None:
    new = par[cur]
    moves.append(cur - new)
    cur = new

moves = list(reversed(moves))
print(" ".join(map(str, moves)))

Submission status: Runtime Error

Solution code:
class segment_tree_dual:
    def __init__(self, N, compose, funcval, ID_M=None):
        self.compose = compose
        self.ID_M = ID_M
        self.funcval = funcval

        self.height = (N-1).bit_length() #木の段数
        self.N0 = 1<<self.height #木の横幅 >= N
        self.laz = [self.ID_M]*(2*self.N0) #作用素の木
        self.val = None #値の配列

    #初期値の配列を作る
    def build(self,initial):
        self.val = initial[:]

    #laz[k] を子に伝える、k が一番下の場合は laz[k] を val に反映する
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        if self.N0 <= k:
            self.val[k-self.N0] = self.funcval(self.val[k-self.N0], self.laz[k])
            self.laz[k] = self.ID_M
        else:
            self.laz[(k<<1)  ] = self.compose(self.laz[(k<<1)  ],self.laz[k]);
            self.laz[(k<<1)+1] = self.compose(self.laz[(k<<1)+1],self.laz[k]);
            self.laz[k] = self.ID_M;
    
    # 遅延をすべて解消する
    def propagate_all(self):
        upto = self.N0 + len(self.val)
        for i in range(1,upto): self.propagate(i)

    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, L,R,f):
        L += self.N0; R += self.N0+1
        """まず伝播させる（オペレータが可換なら必要ない）"""
        #self.thrust(L)
        #self.thrust(R-1)
        #登りながら関数 f を合成
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R],f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L],f)
                L += 1
            L >>= 1; R >>= 1
    
    # values[k] を取得。
    def point_get(self, k):
        res = self.val[k]
        k += self.N0
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k //= 2
        return res
    
    # values[k] = x 代入する
    def point_set(self, k): 
        self.thrust(k+self.N0)
        self.val[k] = x

###########################################################################
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n,m = [int(i) for i in readline().split()]
s = input()[::-1]

compose = min
funcval = min
ID_M = INF = 10**18

seg = segment_tree_dual(n, compose, funcval, ID_M)
seg.build([0]+[INF]*(n))

for i in range(n):
    if s[i] == "1": seg.val[i] = -1
    else:
        v = seg.point_get(i)
        #print(v,i)
        seg.update(i+1,min(n,i+m),v+1)
        #print(seg.laz)

seg.propagate_all()
#print(s)
#print(seg.val)

val = seg.val
if val[-1] == -1 or val[-1] == INF:
    print(-1)
    exit()

ans = []

now = n
time = val[-1]
while now:
    n2 = now-1
    time -= 1
    while s[n2] == "1" or val[n2] != time:
        n2 -= 1
    ans.append(now-n2)
    now = n2
    
print(*ans)

Submission status: Runtime Error

Solution code:
class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


def solve(n, m, s):
    INF = 10 ** 18
    sgt = SegTreeMin(n + 1, (INF,))
    sgt.update(0, (0, 0))
    for i in range(1, n + 1):
        if s[i] == '1':
            continue
        r = i
        l = max(0, i - m)
        prev = sgt.get_min(l, r)
        if prev[0] == INF:
            return (-1,)
        dice = i - prev[-1]
        curr = (prev[0] + 1, *prev[1:-1], dice, i)
        sgt.update(i, curr)
    return sgt.get_min(n, n + 1)[1:-1]


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