Submission #8619541


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300100;
int n;
pair<int,int> seg[maxn], ans[maxn];
void upd(int p, int v){
	for(seg[p += n] = {v, p}; p > 1; p >>= 1)
		seg[p>>1] = min(seg[p], seg[p ^ 1]);
}
pair<int,int> qry(int l, int r){
	pair<int,int> ans = {1<<30, 1<<30};
	for(l += n, r += n; l < r; l >>= 1, r >>= 1){
		if(l&1) ans = min(ans, seg[l++]);
		if(r&1) ans = min(ans, seg[--r]);
	}
	return ans;
}
int main(){
	int m; cin >> n >> m;
	string s; cin >> s;
	n++;
	upd(n - 1, 0);
	for(int i = n - 2; i >= 0; i--){
		pair<int,int> b = {1<<30, 1<<30};
		if(s[i] == '0'){
			b = qry(i + 1, min(i + m + 1, n));
		}
		b.first++;
		upd(i, b.first);
		ans[i] = b;
	}
	if(ans[0].first >= (1<<30)) cout << -1 << endl;
	else {
		int p = 0;
		while(p != n - 1){
			cout << ans[p].second - p << " ";
			p = ans[p].second;
		}
		cout << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task F - Sugoroku
User FMota
Language C++14 (GCC 5.4.1)
Score 600
Code Size 915 Byte
Status AC
Exec Time 22 ms
Memory 3456 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 60
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 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
Case Name Status Exec Time Memory
00-sample-00 AC 2 ms 2304 KB
00-sample-01 AC 2 ms 2304 KB
00-sample-02 AC 2 ms 2304 KB
01-handmade-03 AC 2 ms 2304 KB
01-handmade-04 AC 18 ms 3328 KB
01-handmade-05 AC 16 ms 3328 KB
01-handmade-06 AC 15 ms 3328 KB
01-handmade-07 AC 14 ms 3328 KB
01-handmade-08 AC 18 ms 3328 KB
01-handmade-09 AC 22 ms 3456 KB
01-handmade-10 AC 15 ms 3328 KB
02-random-11 AC 19 ms 3200 KB
02-random-12 AC 15 ms 3328 KB
02-random-13 AC 18 ms 3200 KB
02-random-14 AC 19 ms 3200 KB
02-random-15 AC 17 ms 3072 KB
02-random-16 AC 15 ms 3200 KB
02-random-17 AC 17 ms 3200 KB
02-random-18 AC 17 ms 3200 KB
02-random-19 AC 17 ms 3200 KB
02-random-20 AC 12 ms 3200 KB
02-random-21 AC 16 ms 3200 KB
02-random-22 AC 19 ms 3328 KB
02-random-23 AC 17 ms 3200 KB
02-random-24 AC 14 ms 3328 KB
02-random-25 AC 16 ms 3200 KB
02-random-26 AC 18 ms 3200 KB
02-random-27 AC 16 ms 3200 KB
02-random-28 AC 12 ms 3072 KB
02-random-29 AC 15 ms 3200 KB
02-random-30 AC 18 ms 3328 KB
02-random-31 AC 18 ms 3328 KB
02-random-32 AC 14 ms 3328 KB
02-random-33 AC 15 ms 3200 KB
02-random-34 AC 17 ms 3200 KB
02-random-35 AC 16 ms 3200 KB
02-random-36 AC 13 ms 3200 KB
02-random-37 AC 13 ms 3200 KB
02-random-38 AC 15 ms 3200 KB
02-random-39 AC 16 ms 3200 KB
02-random-40 AC 13 ms 3200 KB
02-random-41 AC 14 ms 3200 KB
02-random-42 AC 15 ms 3200 KB
02-random-43 AC 16 ms 3328 KB
02-random-44 AC 13 ms 3200 KB
02-random-45 AC 15 ms 3200 KB
02-random-46 AC 16 ms 3328 KB
02-random-47 AC 14 ms 3200 KB
02-random-48 AC 12 ms 3200 KB
02-random-49 AC 14 ms 3200 KB
02-random-50 AC 13 ms 3200 KB
02-random-51 AC 14 ms 3200 KB
02-random-52 AC 13 ms 3200 KB
02-random-53 AC 13 ms 3200 KB
02-random-54 AC 14 ms 3200 KB
02-random-55 AC 13 ms 3200 KB
02-random-56 AC 12 ms 3200 KB
02-random-57 AC 14 ms 3328 KB
02-random-58 AC 12 ms 3200 KB
02-random-59 AC 12 ms 3200 KB