#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n, k;
pair <int, int> a[200005], b[200005];
string s;
deque <int> dq;
int main() {
cin >> n >> k >> s;
s = ' ' + s;
int rez = n + 1;
a[0] = {1e9, 0};
for (int i = 1; i <= n; ++i) {
a[i] = a[i - 1];
if (s[i] != 'J')
continue;
if (dq.size() == k)
dq.pop_front();
dq.push_back(i);
if (dq.size() == k)
a[i] = {dq.back() - dq.front() - (k - 1), dq.back() + 1};
}
dq.clear();
b[n + 1] = {1e9, 0};
for (int i = n; i >= 1; --i) {
b[i] = b[i + 1];
if (s[i] != 'I')
continue;
if (dq.size() == k)
dq.pop_back();
dq.push_front(i);
if (dq.size() == k)
b[i] = {dq.back() - dq.front() - (k - 1), dq.front() - 1};
}
dq.clear();
for (int i = 1; i <= n; ++i) {
if (s[i] != 'O')
continue;
if (dq.size() == k)
dq.pop_front();
dq.push_back(i);
if (dq.size() == k) {
int nrj = a[dq.front() - 1].first, posj = a[dq.front() - 1].second;
int nri = b[dq.back() + 1].first, posi = b[dq.back() + 1].second;
if (nrj != 1e9 && nri != 1e9)
rez = min(rez, nri + nrj + dq.back() - dq.front() + 1 - k + posi - dq.back() + dq.front() - posj);
}
}
if (rez == n + 1)
rez = -1;
cout << rez;
return 0;
}
Compilation message
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:20:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
20 | if (dq.size() == k)
| ~~~~~~~~~~^~~~
ho_t2.cpp:23:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
23 | if (dq.size() == k)
| ~~~~~~~~~~^~~~
ho_t2.cpp:32:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
32 | if (dq.size() == k)
| ~~~~~~~~~~^~~~
ho_t2.cpp:35:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
35 | if (dq.size() == k)
| ~~~~~~~~~~^~~~
ho_t2.cpp:42:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | if (dq.size() == k)
| ~~~~~~~~~~^~~~
ho_t2.cpp:45:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
45 | if (dq.size() == k) {
| ~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
312 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
316 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
312 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
316 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
320 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
312 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
332 KB |
Output is correct |
| 33 |
Correct |
1 ms |
332 KB |
Output is correct |
| 34 |
Correct |
1 ms |
316 KB |
Output is correct |
| 35 |
Correct |
1 ms |
316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
312 KB |
Output is correct |
| 11 |
Correct |
1 ms |
312 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
316 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
320 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
312 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
332 KB |
Output is correct |
| 33 |
Correct |
1 ms |
332 KB |
Output is correct |
| 34 |
Correct |
1 ms |
316 KB |
Output is correct |
| 35 |
Correct |
1 ms |
316 KB |
Output is correct |
| 36 |
Correct |
13 ms |
3624 KB |
Output is correct |
| 37 |
Correct |
12 ms |
3880 KB |
Output is correct |
| 38 |
Correct |
14 ms |
3896 KB |
Output is correct |
| 39 |
Correct |
15 ms |
3836 KB |
Output is correct |
| 40 |
Correct |
11 ms |
3868 KB |
Output is correct |
| 41 |
Correct |
12 ms |
3968 KB |
Output is correct |
| 42 |
Correct |
12 ms |
3948 KB |
Output is correct |
| 43 |
Correct |
8 ms |
2532 KB |
Output is correct |
| 44 |
Correct |
10 ms |
3116 KB |
Output is correct |
| 45 |
Correct |
14 ms |
3992 KB |
Output is correct |
| 46 |
Correct |
11 ms |
3872 KB |
Output is correct |
| 47 |
Correct |
12 ms |
3860 KB |
Output is correct |
| 48 |
Correct |
13 ms |
3856 KB |
Output is correct |
| 49 |
Correct |
11 ms |
2736 KB |
Output is correct |
| 50 |
Correct |
12 ms |
3860 KB |
Output is correct |
| 51 |
Correct |
13 ms |
3888 KB |
Output is correct |
| 52 |
Correct |
12 ms |
3940 KB |
Output is correct |
| 53 |
Correct |
14 ms |
3996 KB |
Output is correct |
| 54 |
Correct |
10 ms |
3856 KB |
Output is correct |
| 55 |
Correct |
12 ms |
3972 KB |
Output is correct |
| 56 |
Correct |
9 ms |
4020 KB |
Output is correct |
