This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define exit exit(false)
#define pause system("PAUSE")
//#define here() cerr << "herewego\n";
#define showe(x) cerr << #x << ": " << x << '\n'
#define shows(x) cerr << #x << ": " << x << ", "
#define ioio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n, k, po, ans = INT_MAX;
string s;
vector <int> J, O, I;
int find_1 (int x) {
int l = 0, r = O.size() - 1;
bool f = 0;
while (l <= r) {
int m = (l + r) >> 1;
if (O[m] >= x) {
r = m-1;
f=1;
} else {
l = m+1;
}
}
if (!f) {
return -1;
}
return (r+1);
}
int find_2 (int x) {
int l = 0, r = I.size() - 1;
bool f = 0;
while (l <= r) {
int m = (l + r) >> 1;
if (I[m] >= x) {
r = m-1;
f=1;
} else {
l = m+1;
}
}
if (!f) {
return -1;
}
return (r+1);
}
signed main () { ioio();
cin >> n >> k;
cin >> s;
for (char x : s) {
if (x == 'J') {
J.push_back(po++);
} else if (x == 'O') {
O.push_back(po++);
} else {
I.push_back(po++);
}
}
for (int i = 0; i < J.size(); i++) {
int Js = J[i];
if (i + k - 1 >= J.size()) {
break;
}
int Jf = J[i+k-1];
int c_1 = (Jf - Js + 1) - k;
int j = find_1(Jf+1);
if (j == -1) {
break;
}
int Os = O[j];
if (j + k - 1 >= O.size()) {
break;
}
int Of = O[j+k-1];
int c_2 = (Of - Os + 1) - k;
int c_3 = Os - Jf - 1;
int l = find_2(Of+1);
if (l == -1) {
break;
}
int Is = I[l];
if (l + k - 1 >= I.size()) {
break;
}
int If = I[l+k-1];
int c_4 = (If - Is + 1) - k;
int c_5 = Is - Of - 1;
ans = min(ans, c_1+c_2+c_3+c_4+c_5);
}
if (ans == INT_MAX) {
cout << "-1";
exit;
}
cout << ans;
// cerr << "\nTime elapsed: " << (clock() + 0.0) / CLOCKS_PER_SEC;
}
Compilation message (stderr)
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:72:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 0; i < J.size(); i++) {
| ~~^~~~~~~~~~
ho_t2.cpp:74:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | if (i + k - 1 >= J.size()) {
| ~~~~~~~~~~^~~~~~~~~~~
ho_t2.cpp:84:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if (j + k - 1 >= O.size()) {
| ~~~~~~~~~~^~~~~~~~~~~
ho_t2.cpp:95:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | if (l + k - 1 >= I.size()) {
| ~~~~~~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |