提出 #8635768


ソースコード 拡げる

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<class V, int NV> struct LazySegTree { // [L,R)
	vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
	void update(int a, int b, V v, int k, int l, int r) {
		push(k, l, r); if (r <= a || b <= l) return;
		if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); }
		else {
			update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r);
			dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}
	V get(int a, int b, int k, int l, int r) {
		push(k, l, r); if (r <= a || b <= l) return def;
		if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
		auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y);
	}
	void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); }
	V get(int a, int b) { return get(a, b, 0, 0, NV); }
	// ---- Template ---------------------------------------------------------------------------------
	// 区間min代入,区間min
	const V def = inf, ldef = inf;
	V comp(V l, V r) { return min(l, r); }
	void setLazy(int i, V v) { lazy[i] = min(lazy[i], v); }
	void push(int k, int l, int r) {
		if (lazy[k] != ldef) {
			// modify------------------------------
			dat[k] = min(dat[k], lazy[k]);
			// ------------------------------------
			if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); }
			lazy[k] = ldef;
		}
	}
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, M; string S;
LazySegTree<int, 1 << 17> lst;
vector<int> idx[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> S;

	lst.update(N, N + 1, 0);
	rrep(i, N, 0) if(S[i] == '0') {
		int mi = lst.get(i, i + 1);
		int l = max(0, i - M);
		lst.update(l, i, mi + 1);
	}
	
	if (lst.get(0, 1) == inf) {
		cout << -1 << endl;
		return;
	}

	rep(i, 0, N + 1) if (S[i] == '0') idx[lst.get(i, i + 1)].push_back(i);

	vector<int> ans;
	int cu = 0;
	int dp = lst.get(0, 1);
	while (cu < N) {
		int nxt = *upper_bound(all(idx[dp - 1]), cu);
		ans.push_back(nxt - cu);
		cu = nxt;
		dp--;
	}

	int n = ans.size();
	rep(i, 0, n) {
		if (i) printf(" ");
		printf("%d", ans[i]);
	}
	printf("\n");
}





提出情報

提出日時
問題 F - Sugoroku
ユーザ hamayanhamayan
言語 C++14 (GCC 5.4.1)
得点 600
コード長 3512 Byte
結果
実行時間 59 ms
メモリ 8648 KB

テストケース

セット名 得点 / 配点 テストケース
Sample 0 / 0 00-sample-00, 00-sample-01, 00-sample-02
All 600 / 600 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49, 02-random-50, 02-random-51, 02-random-52, 02-random-53, 02-random-54, 02-random-55, 02-random-56, 02-random-57, 02-random-58, 02-random-59
ケース名 結果 実行時間 メモリ
00-sample-00 3 ms 4736 KB
00-sample-01 3 ms 4736 KB
00-sample-02 3 ms 4736 KB
01-handmade-03 3 ms 4736 KB
01-handmade-04 55 ms 5328 KB
01-handmade-05 54 ms 5584 KB
01-handmade-06 9 ms 5072 KB
01-handmade-07 4 ms 4992 KB
01-handmade-08 34 ms 5072 KB
01-handmade-09 59 ms 8648 KB
01-handmade-10 32 ms 4992 KB
02-random-11 49 ms 5372 KB
02-random-12 31 ms 4992 KB
02-random-13 53 ms 5120 KB
02-random-14 56 ms 5248 KB
02-random-15 41 ms 5248 KB
02-random-16 46 ms 5632 KB
02-random-17 48 ms 5376 KB
02-random-18 47 ms 5120 KB
02-random-19 41 ms 5248 KB
02-random-20 24 ms 4864 KB
02-random-21 45 ms 5120 KB
02-random-22 49 ms 5200 KB
02-random-23 37 ms 5248 KB
02-random-24 26 ms 4864 KB
02-random-25 41 ms 5248 KB
02-random-26 45 ms 5120 KB
02-random-27 32 ms 5248 KB
02-random-28 20 ms 4864 KB
02-random-29 34 ms 5120 KB
02-random-30 40 ms 5072 KB
02-random-31 38 ms 5200 KB
02-random-32 21 ms 4864 KB
02-random-33 32 ms 4992 KB
02-random-34 34 ms 4992 KB
02-random-35 28 ms 5248 KB
02-random-36 18 ms 4864 KB
02-random-37 25 ms 4992 KB
02-random-38 28 ms 4992 KB
02-random-39 28 ms 4992 KB
02-random-40 16 ms 4864 KB
02-random-41 24 ms 4992 KB
02-random-42 25 ms 4992 KB
02-random-43 21 ms 5248 KB
02-random-44 14 ms 4864 KB
02-random-45 22 ms 4992 KB
02-random-46 22 ms 4992 KB
02-random-47 17 ms 4992 KB
02-random-48 10 ms 4864 KB
02-random-49 17 ms 4864 KB
02-random-50 15 ms 4864 KB
02-random-51 15 ms 4864 KB
02-random-52 9 ms 4864 KB
02-random-53 12 ms 4864 KB
02-random-54 12 ms 4864 KB
02-random-55 10 ms 4864 KB
02-random-56 6 ms 4864 KB
02-random-57 8 ms 4992 KB
02-random-58 6 ms 4864 KB
02-random-59 5 ms 4864 KB