#include <bits/stdc++.h>
#define int long long
#define pp pop_back
#define pb push_back
#define eb emplace_back
#define nl cout "\n"
#define sp <<" "
#define spc <<" "<<
#define ff first
#define ss second
#define r0 return 0
#define INF INT_MAX
#define mod 998244353
#define MOD 1000000007
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define vll vector<ll>
#define vb vector<bool>
#define vd vector<double>
#define vs vector<string>
#define pii pair <int,int>
#define pll pair<ll,ll>
#define pls pair<ll,string>
#define psl pair<string,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define pss pair<string,string>
#define pis pair<int,string>
#define sz size()
#define pause system("pause")
#define min3(a,b,c) min(a,min(b,c))
#define all(x) (x).begin(),(x).end()
#define deb(x) cout << #x << " - " << x << endl
using namespace std;
vector <int> vj;
vector <int> vi;
vector <int> vo;
inline void test_case(){
int ans=INT_MAX;
int n, k;
cin >> n >> k;
string s;
cin >> s;
vi.pb(-1);
for(int i=0; i<n; i++){
if(s[i]=='J'){
vj.pb(i);
}
if(s[i]=='O'){
vo.pb(i);
}
if(s[i]=='I'){
vi.pb(i);
}
}
vj.pb(INT_MAX);
// cout << vj[1];
// cout << vo.size()-k+1 << endl;
for(int i=0; i<vo.size()-k+1; i++){
int check=0;
int l=vo[i];
int r=vo[i+k-1];
int je;
int start=0;
int end=vj.size()-1;
while(start<end){
int mid=(start+end)/2;
// deb(mid);
if(vj[mid]<l && vj[mid+1]>l){
je=mid;
check=1;
break;
}
if(vj[mid+1]<l){
start=mid+1;
continue;
}
end=mid;
}
// deb(check);
if(check==0){
continue;
}
// cout << vj[je] << endl;
int js=je-k+1;
// cout << vj[js] << endl;
check=0;
int is;
start=0;
end=vi.size()-1;
while(start<end){
int mid=(start+end)/2;
// deb(mid);
if(vi[mid]>r && vi[mid-1]<r){
is=mid;
check=1;
break;
}
if(vi[mid]>r){
end=mid;
continue;
}
start=mid+1;
}
if(check==0){
continue;
}
// cout << vi[is] << endl;
int ie=is+k-1;
// cout << vi[ie] << endl;
ans=min(ans, vi[ie]-vj[js]-3*k+1);
}
if(ans==INT_MAX){
cout << -1 << endl;
}
else{
cout << ans;
}
}
signed main () {
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
test_case();
}
return 0;
}
Compilation message
ho_t2.cpp: In function 'void test_case()':
ho_t2.cpp:59:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
59 | for(int i=0; i<vo.size()-k+1; i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
