//srand(time(0)) - always changing
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const int P = 911;
const ll INF = 1e18;
int gcd(int a, int b) {
while (b) {
a %= b;
swap (a, b);
}
return a;
}
ll __sqrt(ll x) {
ll result = 0;
for (ll k = 1ll << 30; k != 0; k >>= 1) {
if ((result + k) * (result + k) <= x) {
result += k;
}
}
return result;
}
int j[N], o[N], i[N];
void solve() {
int n, k, numj = 0, numo = 0, numi = 0, ans = INF;
string s;
cin >> n >> k >> s;
for (int idx = 0; idx < n; idx++) {
if (s[idx] == 'J') {
j[++numj] = idx;
}
if (s[idx] == 'O') {
o[++numo] = idx;
}
if (s[idx] == 'I') {
i[++numi] = idx;
}
}
for (int idx = 0; idx + k - 1 <= numj; idx++) {
// cout << idx << '\n';
int l = 1, r = numo, need = j[idx + k - 1];
while (l <= r) {
int m = l + r >> 1;
if (o[m] < need) l = m + 1;
else r = m - 1;
}
if (o[l] < need || l + k - 1 > numo) {
break;
}
need = o[l + k - 1];
l = 1;
r = numi;
while (l <= r) {
int m = l + r >> 1;
if (i[m] < need) l = m + 1;
else r = m - 1;
}
if (i[l] < need || l + k - 1 > numi) {
break;
} else {
ans = min(ans, i[l + k - 1] - j[idx] + 1 - k * 3);
// cout << idx << ' ' << j[idx] << ' ' << j[idx + k - 1] << ' ' << i[l] << ' ' << i[l + k - 1] << '\n';
}
// cout << idx << '\n';
}
if (ans == INF) ans = -1;
cout << ans;
}
const bool Cases = 0;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TT = 1;
if (Cases) cin >> TT;
while (TT--) {
solve();
}
}
Compilation message
ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int m = l + r >> 1;
| ~~^~~
ho_t2.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int m = l + r >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
