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>
//#ifndef ONLINE_JUDGE
//#include <debugging.h>
//#endif
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
#define dbg(v) cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
using pld = pair <ld,ld>;
const char el ='\n';
const char sp = ' ';
const int maxn = 2e5+5, mod = 1e9+7, N = 10;
const ll inf = 1e9L+3;
int n,k,cnt[3][maxn];
string s;
int id (char c)
{
if(c=='J') return 0;
if(c=='O') return 1;
if(c=='I') return 2;
}
void input()
{
cin>>n>>k>>s;
s = '*' + s;
for(int i=1;i<=n;++i) ++cnt[id(s[i])][i];
for(int i=0;i<3;++i)
for(int j=1;j<=n;++j) cnt[i][j]+=cnt[i][j-1];
}
void solve()
{
int ans = inf;
for(int i=1;i<=n;++i)
{
// dbg(i);
if(s[i]!='J') continue;
int l = i, r = n, mid;
while(l<=r)
{
mid = (l+r)/2;
if(cnt[0][mid] - cnt[0][i-1] >=k) r=mid-1;
else l=mid+1;
}
// cout<<l<<sp;
if(cnt[0][l] - cnt[0][i-1]<k) continue;
r = n;
int le = l;
while(l<=r)
{
mid = (l+r)/2;
if(cnt[1][mid] - cnt[1][le-1]>=k) r=mid-1;
else l=mid+1;
}
// cout<<l<<sp;
if(cnt[1][l] - cnt[1][le-1]<k) continue;
r=n;
le = l;
while(l<=r)
{
mid = (l+r)/2;
if(cnt[2][mid] - cnt[2][le-1]>=k) r=mid-1;
else l=mid+1;
}
// cout<<l<<sp;
if(cnt[2][l] - cnt[2][le-1]<k) continue;
// cout<<"666"<<sp;
ans = min(ans, l-i+1-3*k);
}
if(ans>=inf) cout<<-1;
else cout<<ans;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
// cin>>test;
while(test-->0)
{
input();
solve();
}
return 0;
}
Compilation message (stderr)
ho_t2.cpp: In function 'int id(char)':
ho_t2.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
28 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |