Submission #8627009

---

Source Code Expand

#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <thread>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

//セグ木
ll dat[2560000], sz;

void init(ll n) {
	sz = 1;
	while (sz < n)sz *= 2;
	REP(i, sz * 2 - 1) dat[i] = INF; //初期値
}

void update(ll k, ll a) { //場所(0-indexed), 値
	k += sz - 1;
	dat[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); //更新
	}
}

ll query(ll a, ll b, ll k, ll l, ll r) { //[a, b) 呼ぶとき (a, b, 0, 0, sz)
	if (r <= a or b <= l)return INF;
	if (a <= l and r <= b)return dat[k];
	ll v1 = query(a, b, k * 2 + 1, l, (l + r) / 2);
	ll v2 = query(a, b, k * 2 + 2, (l + r) / 2, r);
	return min(v1, v2); //戻り値
}

ll n, m, dp[210000], t, now;
string s;
vector<P> l;
vector<ll> ans;
int main() {
	init(210000);
	cin >> n >> m;
	cin >> s;
	update(0, 0);
	REPO(i, n) {
		if (s[i] != '1') {
			update(i, query(max(0ll, i - m), i, 0, 0, sz) + 1);
		}
	}
	if (query(n, n + 1, 0, 0, sz) >= INF) {
		cout << -1 << endl;
		return 0;
	}
	else t = query(n, n + 1, 0, 0, sz);
	REP(i, n + 1) {
		if (s[i] != '1') {
			l.push_back(P(query(i, i + 1, 0, 0, sz), i));
		}
	}
	//REP(i, l.size())cout << l[i].first << " " << l[i].second << endl;
	REP(i, l.size()) {
		if (l[i].first == t - 1) {
			ans.push_back(n - l[i].second);
			break;
		}
		now += l[i + 1].second - l[i].second;
		if (l[i].first != l[i + 1].first) {
			ans.push_back(now);
			now = 0;
		}
	}
	REP(i, ans.size()) {
		if (i != 0)cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

Submission Info

Judge Result