Submission #1133288

#TimeUsernameProblemLanguageResultExecution timeMemory
1133288MunkhturErdenebatJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
12 ms3020 KiB
#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
#include <stdlib.h>
 #define ll long long
using namespace std;
    ll k[5][100000],a,b,c,d,e,f,m,i,j,n,h,g,l,r,ka,p,q,t[200005];
    map<ll,ll> maa,mii,mee;
    vector<ll> vj,vo,vi;
    string x,y,z;

int main(){
    cin>>a>>b;
    cin>>x;
    for(i=0 ; i<a ; i++){
        if(x[i]=='J'){
            vj.push_back(i);
        }
        if(x[i]=='O'){
            vo.push_back(i);
        }
        if(x[i]=='I'){
            vi.push_back(i);
        }
    }
    if(vj.size()<b){
        cout<<-1;
        return 0;
    }
    if(vo.size()<b){
        cout<<-1;
        return 0;
    }
    if(vi.size()<b){
        cout<<-1;
        return 0;
    }
    h=-1;
    for(i=0 ; i<vo.size()-b+1 ; i++){
        if(vo[i]>vj[b-1]){
            h=i;
            break;
        }
    }
    if(h==-1){
        cout<<h;
        return 0;
    }
    if(vo[h+b-1]>vi[vi.size()-b]){
        cout<<-1;
        return 0;
    }
    h=100000000000;
    for(i=0 ; i<vj.size()-b+1 ; i++){
        n=vj[i+b-1];
        l=0;
        r=vo.size()-b;
        if(vo[r]<n){
            break;
        }
        while(l<r){
            m=(l+r-1)/2;
            if(vo[m]>n){
                r=m;
            }
            else{
                l=m+1;
            }
        }
        n=vo[l+b-1];
        l=0;
        r=vi.size()-b;
        if(vi[r]<n){
            break;
        }
        while(l<r){
            m=(l+r-1)/2;
            if(vi[m]>n){
                r=m;
            }
            else{
                l=m+1;
            }
            
        }
        l+=b-1;
        h=min(h,(a-3*b-vj[i]-(a-vi[l]-1)));
    }
    cout<<h<<endl;
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...