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>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5+5;
int cntj[N], cnto[N], cnti[N];
signed main(){
fastio
int n,k;
cin >> n >> k;
string s;
cin >> s;
s = '$' + s;
cntj[n+1] = cnto[n+1] = cnti[n+1] = 1e18;
for(int i = 1;i <= n;i++){
cntj[i] = cntj[i-1], cnto[i] = cnto[i-1], cnti[i] = cnti[i-1];
if(s[i]=='J'){
cntj[i]++;
}else if(s[i]=='O'){
cnto[i]++;
}else if(s[i]=='I'){
cnti[i]++;
}
}
auto check = [&](int i, int j){
int idx = lower_bound(cntj+1,cntj+n+1,cntj[i-1]+k)-cntj;
if(idx >= j) return false;
idx = lower_bound(cnto+1,cnto+n+1,cnto[idx-1]+k)-cnto;
if(idx >= j) return false;
idx = lower_bound(cnti+1,cnti+n+1,cnti[idx-1]+k)-cnti;
if(idx > j) return false;
else return true;
};
int ans = 1e18;
for(int i = 1;i <= n;i++){
int l = i, r = n;
while(l < r){
int mid = l+r>>1;
if(check(i,mid)) r = mid;
else l = mid+1;
}
if(check(i,l)){
ans = min(l-i+1-k*3,ans);
}
}
cout << (ans==1e18 ? -1 : ans) << "\n";
}
Compilation message (stderr)
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid = l+r>>1;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |