#include "bits/stdc++.h"
#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'
int main() {
#ifdef mlocal
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k; cin >> n >> k;
string s; cin >> s;
vi pref(n);
vector<deque<int>> prefpos(3*n);
for_(i, 0, n) {
if (s[i] == 'c') pref[i] = -k;
else pref[i] = 1;
if (i) pref[i] += pref[i-1];
prefpos[pref[i]+n].push_back(i);
}
function<void(int, int)> solve = [&] (int l, int r) {
if (l > r) return;
// cout << "solving " << l << " " << r << endl;
int prepref = (l > 0 ? pref[l-1] : 0);
// cout << "\tgot previous prefix: " << prepref << endl;
assert(pref[r] == prepref);
for_(split, l, r) {
if (pref[split] == prepref) {
solve(l, split);
solve(split+1, r);
return;
}
}
for (int opt = k+1; opt >= 0; opt--) {
int va = (l+opt-1 >= 0 ? pref[l+opt-1] : 0) - prepref;
int sufopt = k+1-opt;
int vb = pref[r] - (r-sufopt >= 0 ? pref[r-sufopt] : 0);
if (va+vb == 0) {
// cout << "works with prefix " << opt << endl;
vi ans;
for_(i, l, l+opt) ans.push_back(i);
for_(i, r-sufopt+1, r+1) ans.push_back(i);
for (auto i: ans) cout << i+1 << " ";
cout << endl;
// cout << "should have gone to " << l+opt << " " << r-sufopt << " from " << l << " " << r << endl;
solve(l+opt, r-sufopt);
return;
}
}
// cout << "uhhh found nothing " << l << " " << r << endl;
// assert(false);
};
solve(0, n-1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - int32 expected |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2764 KB |
Output is correct |
2 |
Incorrect |
2 ms |
3532 KB |
Unexpected end of file - int32 expected |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16476 KB |
Output is correct |
2 |
Correct |
12 ms |
20428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
31 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
31 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
37 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
36 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
33 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |