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 <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifdef __APPLE__
#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif
void solve() {
int n, k;
string s;
cin >> n >> k >> s;
vector<int> pos_j, pos_i;
for (int i = 0; i < n; ++i) {
if (s[i] == 'J') {
pos_j.emplace_back(i);
}
}
for (int i = n - 1; i > -1; --i) {
if (s[i] == 'I') {
pos_i.emplace_back(i);
}
}
if (sz(pos_j) < k || sz(pos_i) < k) {
cout << -1 << en;
}
vector<int> pos_o;
for (int i = pos_j[k - 1] + 1; i < pos_i[k - 1]; ++i) {
if (s[i] == 'O') {
pos_o.emplace_back(i);
}
}
if (sz(pos_o) < k) {
cout << -1 << en;
return;
}
int ans = n;
reverse(all(pos_i));
// int ptr_j = k - 1, ptr_o = 0, ptr_i = 0;
// while (pos_i[ptr_i] < pos_o[ptr_o + k - 1]) {
// ++ptr_i;
// }
//
// pos_j.emplace_back(-1);
// pos_i.emplace_back(n + 1);
//
// while (ptr_j < sz(pos_j) && ptr_o + k - 1 < sz(pos_o) && ptr_i + k - 1 < sz(pos_i)) {
// int l = pos_j[ptr_j - k + 1], r = pos_i[ptr_i + k - 1];
// ans = min(ans, r - l + 1 - 3 * k);
// ++ptr_o;
// if (!(ptr_o + k - 1 < sz(pos_o))) {
// break;
// }
// while (ptr_i < sz(pos_i) && pos_i[ptr_i] < pos_o[ptr_o + k - 1]) {
// ++ptr_i;
// }
// while (ptr_j + 1 < sz(pos_j) && pos_o[ptr_o] < pos_j[ptr_j + 1]) {
// ++ptr_j;
// }
// }
for (int i = 0; i + k - 1 < sz(pos_o); ++i) {
int o1 = pos_o[i], o2 = pos_o[i + k - 1];
int id_j = (int)(lower_bound(all(pos_j), o1) - pos_j.begin());
--id_j;
// while (id_j > -1 && o1 < pos_j[id_j]) {
// --id_j;
// }
if (id_j - k + 1 < 0) {
continue;
}
int id_i = (int)(lower_bound(all(pos_i), o2) - pos_i.begin());
if (id_i + k - 1 >= sz(pos_i)) {
continue;
}
int l = pos_j[id_j - k + 1], r = pos_i[id_i + k - 1];
ans = min(ans, r - l + 1 - 3 * k);
}
cout << ans << en;
}
int main() {
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |