# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503566 |
2022-01-08T10:45:45 Z |
gaspar |
JJOOII 2 (JOI20_ho_t2) |
C++14 |
|
15 ms |
4020 KB |
#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) {
| ~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |