Language: C++

/**
 * Created by hiramekun at 21:40 on 2019-11-24.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template <typename T> using pq = priority_queue<T>;
template <typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto &i : mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

using data = pair<P, ll>;

template <class T> ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template <class T> istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template <class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
// sample: http://beet-aizu.hatenablog.com/entry/2017/12/01/225955
// verified with
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_F
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G
template <typename Data, typename Lazy> struct SegmentTree {
  public:
    bool isLazy = false;
    int sz;
    vector<Data> seg;
    vector<Lazy> lazy;

    // mergeするときの操作
    using MergeData = function<Data(Data, Data)>;
    // lazyをxでupdate
    using UpdateLazyFromX = function<Lazy(Lazy, Lazy)>;
    // dataをlazyでupdate
    using UpdateDataFromLazy = function<Data(Data, Lazy)>;
    // lenが与えられた時にlazyを計算
    using CalcLazyWithLen = function<Lazy(Lazy, ll)>;

    // lazy
    // O(N)
    SegmentTree(int n, const MergeData fm, const UpdateLazyFromX fl,
                const UpdateDataFromLazy fa, const CalcLazyWithLen fw, Data M1,
                Lazy A1)
        : fm(fm), fl(fl), fa(fa), fw(fw), M1(M1), A1(A1) {
        isLazy = true;
        sz = 1;
        while(sz < n)
            sz *= 2;
        seg.assign(2 * sz - 1, M1);
        lazy.assign(2 * sz - 1, A1);
    }

    // not lazy
    SegmentTree(int n, const MergeData fm, Data M1)
        : fm(fm), M1(M1),
          // ここからdummy
          fl([M1](P a, P b) { return M1; }), fa([M1](P a, P b) { return M1; }),
          fw([M1](P a, ll b) { return M1; }), A1(M1) {
        isLazy = false;
        sz = 1;
        while(sz < n)
            sz *= 2;
        seg.assign(2 * sz - 1, M1);
    }

    // not lazy
    // O(logN)
    Data update(int i, Data x) {
        i += sz - 1;
        seg[i] = x;
        while(i > 0) {
            i = (i - 1) / 2;
            seg[i] = fm(seg[2 * i + 1], seg[2 * i + 2]);
        }
    }

    void build(const vector<Data> &v) {
        ll n = v.size();
        rep(i, n) seg[i + sz - 1] = v[i];
        for(ll i = sz - 2; i >= 0; --i) {
            seg[i] = fm(seg[i * 2 + 1], seg[i * 2 + 2]);
        }
    }

    // for lazy only
    // O(logN)
    Data update(int a, int b, Data x) { return update(a, b, x, 0, 0, sz); }

    // O(logN)
    Data query(int a, int b) { return query(a, b, 0, 0, sz); }

  private:
    const MergeData fm;
    const UpdateLazyFromX fl;
    const UpdateDataFromLazy fa;
    const CalcLazyWithLen fw;
    const Data M1;
    const Lazy A1;

    void eval(int len, int k) {
        if(lazy[k] == A1)
            return;
        if(k * 2 + 1 < sz * 2 - 1) {
            lazy[2 * k + 1] = fl(lazy[2 * k + 1], lazy[k]);
            lazy[2 * k + 2] = fl(lazy[2 * k + 2], lazy[k]);
        }
        seg[k] = fa(seg[k], fw(lazy[k], len));
        lazy[k] = A1;
    }

    Data update(int a, int b, Data x, int k, int l, int r) {
        eval(r - l, k);
        if(r <= a || b <= l)
            return seg[k];
        if(a <= l && r <= b) {
            lazy[k] = fl(lazy[k], x);
            return fa(seg[k], fw(lazy[k], r - l));
        }
        return seg[k] = fm(update(a, b, x, k * 2 + 1, l, (l + r) / 2),
                           update(a, b, x, k * 2 + 2, (l + r) / 2, r));
    }

    Data query(int a, int b, int k, int l, int r) {
        if(isLazy)
            eval(r - l, k);
        if(r <= a || b <= l)
            return M1;
        if(a <= l && r <= b)
            return seg[k];
        Data vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        Data vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return fm(vl, vr);
    }
};

int main() {
    ll n, m;
    string S;
    cin >> n >> m;
    cin >> S;
    // 1からMまでのM種類の目がでるルーレット
    // dp[i]:startからマスiにたどり着くのに必要な最小歩数
    // segtreeでもとめれる
    vector<ll> dp(n + 1, 0LL);
    rep(i, S.length()) {
        if(S[i] == '1') {
            dp[i] = ll_inf;
        }
    }
    SegmentTree<P, P> tree(n + 1, [](P a, P b) { return min(a, b); },
                           P(ll_inf, ll_inf));
    dp[0] = 0;
    tree.update(0, P(0, 0));
    vl prev_i(n + 1); //経路復元のため
    for(int i = 1; i < n + 1; i++) {
        if(S[i] == '1') {
            continue;
        }
        ll index = max(i - M, 0LL);
        P p = tree.query(index, i + 1);
        ll cost = p.F;
        ll idx = p.S;
        dp[i] = cost + 1;
        tree.update(i, P(dp[i], i));
        prev_i[i] = idx;
    }
    // REP(i, N + 1) { cout << tree.get(i) << endl; }
    if(dp[n] == ll_inf || dp[n] >= ll_inf) {
        cout << -1 << endl;
        return 0;
    }
    vl ans;
    ll now = n;
    while(now > 0) {
        ans.eb(now - prev_i[now]);
        now = prev_i[now];
    }
    reverse(all(ans));
    cout << ans << '\n';
    return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:194:28: error: 'M' was not declared in this scope
  194 |         ll index = max(i - M, 0LL);
      |                            ^
a.cc: In instantiation of 'Data SegmentTree<Data, Lazy>::update(int, Data) [with Data = std::pair<long long int, long long int>; Lazy = std::pair<long long int, long long int>]':
a.cc:188:16:   required from here
  188 |     tree.update(0, P(0, 0));
      |     ~~~~~~~~~~~^~~~~~~~~~~~
a.cc:110:5: warning: no return statement in function returning non-void [-Wreturn-type]
  110 |     }
      |     ^