제출 #770650

#제출 시각아이디문제언어결과실행 시간메모리
770650nihonJJOOII 2 (JOI20_ho_t2)C++14
100 / 100
11 ms1616 KiB
#include <bits/stdc++.h>
#define N 200005
using namespace std;
string s;
char ch;
int n,k,i,l,st,dr,mid,sol,b,e,x;
int J[N],O[N],I[N],tj,to,ti;
int mn=2e9;
int main()
{
    cin>>n>>k>>s;
    l=s.size();
    for(i=0;i<l;i++)
    {
        ch=s[i];
        if(ch=='J')
        {
            J[++tj]=i;
        }
        if(ch=='O')
        {
            O[++to]=i;
        }
        if(ch=='I')
        {
            I[++ti]=i;
        }
    }
    for(i=1;i<=tj;i++)
    {
        if(i+k-1>tj) break;
        b=J[i];
        x=J[i+k-1]+1;
        if(x>=l) continue;
        st=1; dr=to; sol=-1;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(O[mid]<x) st=mid+1;
            else {sol=mid; dr=mid-1;}
        }
        if(sol<0 || sol+k-1>to) continue;
        x=O[sol+k-1]+1;
        if(x>=l) continue;
        st=1; dr=ti; sol=-1;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(I[mid]<x) st=mid+1;
            else {sol=mid; dr=mid-1;}
        }
        if(sol<0 || sol+k-1>ti) continue;
        e=I[sol+k-1];
        mn=min(mn,(e-b+1)-3*k);
    }
    if(mn==2e9) cout<<-1;
    else cout<<mn;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...