# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
241606 |
2020-06-24T17:47:18 Z |
verngutz |
JJOOII 2 (JOI20_ho_t2) |
C++14 |
|
13 ms |
4476 KB |
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
string s;
cin >> s;
int ans = lim<int>::max();
vector<int> J, O, I, jumpJ(n + 1, -1), jumpO(n + 1, -1), jumpI(n + 1, -1);
for(int i = 0; i < n; i++) {
if(s[i] == 'J') {
J.push_back(i);
} else if(s[i] == 'O') {
O.push_back(i);
} else {
I.push_back(i);
}
}
for(int i = (k - 1 < J.size() ? J[k - 1] + 1 : n), j = 0; i < n; i++) {
jumpJ[i] = J[j];
if(s[i] == 'J') {
j++;
}
}
for(int i = (O.size() - k >= 0 ? O[O.size() - k] - 1 : -1), j = O.size() - 1; i >= 0; i--) {
jumpO[i] = O[j];
if(s[i] == 'O') {
j--;
}
}
for(int i = (I.size() - k >= 0 ? I[I.size() - k] - 1 : -1), j = I.size() - 1; i >= 0; i--) {
jumpI[i] = I[j];
if(s[i] == 'I') {
j--;
}
}
for(int i = 1; i < n; i++) {
if(s[i] == 'O') {
int j = jumpO[i - 1];
if(jumpJ[i] != -1 and jumpO[i - 1] != -1 and jumpI[j] != -1) {
ans = min(ans, (i - jumpJ[i]) + (j - i + 1) + (jumpI[j] - j) - 3 * k);
}
}
}
cout << (ans < lim<int>::max() ? ans : -1) << endl;
return 0;
}
Compilation message
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = (k - 1 < J.size() ? J[k - 1] + 1 : n), j = 0; i < n; i++) {
~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
256 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
256 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
5 ms |
384 KB |
Output is correct |
31 |
Correct |
5 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |
34 |
Correct |
5 ms |
384 KB |
Output is correct |
35 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
256 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
5 ms |
384 KB |
Output is correct |
31 |
Correct |
5 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
5 ms |
384 KB |
Output is correct |
34 |
Correct |
5 ms |
384 KB |
Output is correct |
35 |
Correct |
5 ms |
384 KB |
Output is correct |
36 |
Correct |
12 ms |
3716 KB |
Output is correct |
37 |
Correct |
11 ms |
4296 KB |
Output is correct |
38 |
Correct |
11 ms |
4340 KB |
Output is correct |
39 |
Correct |
13 ms |
4356 KB |
Output is correct |
40 |
Correct |
12 ms |
4432 KB |
Output is correct |
41 |
Correct |
12 ms |
4460 KB |
Output is correct |
42 |
Correct |
12 ms |
4228 KB |
Output is correct |
43 |
Correct |
9 ms |
2912 KB |
Output is correct |
44 |
Correct |
10 ms |
3316 KB |
Output is correct |
45 |
Correct |
11 ms |
4356 KB |
Output is correct |
46 |
Correct |
12 ms |
4348 KB |
Output is correct |
47 |
Correct |
13 ms |
4356 KB |
Output is correct |
48 |
Correct |
11 ms |
4476 KB |
Output is correct |
49 |
Correct |
9 ms |
2828 KB |
Output is correct |
50 |
Correct |
11 ms |
4228 KB |
Output is correct |
51 |
Correct |
11 ms |
4228 KB |
Output is correct |
52 |
Correct |
10 ms |
3912 KB |
Output is correct |
53 |
Correct |
11 ms |
4296 KB |
Output is correct |
54 |
Correct |
9 ms |
4356 KB |
Output is correct |
55 |
Correct |
9 ms |
4356 KB |
Output is correct |
56 |
Correct |
9 ms |
4356 KB |
Output is correct |