Contest Duration: - (local time) (100 minutes) Back to Home

Submission #8627009

Source Code Expand

Copy
```#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>

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

Submission Time 2019-11-24 22:15:19+0900 F - Sugoroku kenken714 C++14 (GCC 5.4.1) 0 2162 Byte WA 53 ms 8432 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
 AC × 3
 AC × 19 WA × 41
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 4736 KB
00-sample-01 AC 2 ms 4736 KB
00-sample-02 AC 2 ms 4736 KB
01-handmade-03 AC 2 ms 4736 KB
01-handmade-04 WA 48 ms 7028 KB
01-handmade-05 WA 47 ms 7028 KB
01-handmade-06 AC 10 ms 5120 KB
01-handmade-07 AC 6 ms 4992 KB
01-handmade-08 WA 30 ms 6008 KB
01-handmade-09 AC 53 ms 8432 KB
01-handmade-10 AC 27 ms 4992 KB
02-random-11 WA 42 ms 7028 KB
02-random-12 AC 26 ms 4992 KB
02-random-13 WA 45 ms 7028 KB
02-random-14 WA 47 ms 7028 KB
02-random-15 WA 36 ms 7028 KB
02-random-16 WA 40 ms 7028 KB
02-random-17 WA 42 ms 7028 KB
02-random-18 WA 40 ms 7028 KB
02-random-19 WA 36 ms 7028 KB
02-random-20 AC 20 ms 4992 KB
02-random-21 WA 40 ms 7028 KB
02-random-22 WA 43 ms 7028 KB
02-random-23 WA 33 ms 7028 KB
02-random-24 AC 21 ms 4992 KB
02-random-25 WA 35 ms 6008 KB
02-random-26 WA 38 ms 7028 KB
02-random-27 WA 28 ms 6008 KB
02-random-28 AC 17 ms 4992 KB
02-random-29 WA 29 ms 6008 KB
02-random-30 WA 35 ms 6008 KB
02-random-31 WA 33 ms 6008 KB
02-random-32 AC 18 ms 4992 KB
02-random-33 WA 28 ms 6008 KB
02-random-34 WA 30 ms 6008 KB
02-random-35 WA 25 ms 6008 KB
02-random-36 AC 15 ms 4992 KB
02-random-37 WA 22 ms 6008 KB
02-random-38 WA 25 ms 6008 KB
02-random-39 WA 24 ms 6008 KB
02-random-40 AC 14 ms 4992 KB
02-random-41 WA 22 ms 6008 KB
02-random-42 WA 22 ms 6008 KB
02-random-43 WA 19 ms 6008 KB
02-random-44 AC 12 ms 4992 KB
02-random-45 WA 19 ms 5500 KB
02-random-46 WA 20 ms 5500 KB
02-random-47 WA 16 ms 5500 KB
02-random-48 AC 10 ms 4992 KB
02-random-49 WA 15 ms 5500 KB
02-random-50 WA 14 ms 5500 KB
02-random-51 WA 14 ms 5500 KB
02-random-52 AC 9 ms 4992 KB
02-random-53 WA 11 ms 5248 KB
02-random-54 WA 12 ms 5248 KB
02-random-55 WA 10 ms 5248 KB
02-random-56 AC 7 ms 4992 KB
02-random-57 WA 9 ms 5120 KB
02-random-58 WA 7 ms 4992 KB
02-random-59 WA 6 ms 4992 KB