Submission #1341854

#TimeUsernameProblemLanguageResultExecution timeMemory
1341854zwheaJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
11 ms8400 KiB
#include <iostream> 
#include <vector> 
#include <string> 
#include <algorithm>
#include <cmath> 
#include <map>                  
#include <set>
#include <queue>    
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric> 
#include <functional>
#include <iomanip>
#include <sstream>
#include <numeric>  
                                                                                
#define endl "\n"
#define int long long
#define pb push_back
#define fi first
#define se second
#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//pragma GCC optimize("unroll-loops")
using namespace std;
int INF=1e18;
int MOD=1e9+7;
int MOD2=1e9;
int ABCMOD=998244353;

//mac olunca template kullanmak zorundayim :/

inline void solve(){
    int n,k; cin>>n>>k;
    string s; cin>>s;

    vector<int> posj(n,-1),poso(n,-1),posi(n,-1);

    int J=0,O=0,I=0;

    for(int i=0;i<n;i++){
        if(s[i]=='J'){
            posj[J]=i;
            J++;
        }
        else if(s[i]=='O'){
            poso[O]=i;
            O++;
        }
        else{
            posi[I]=i;
            I++;
        }
    }
    
/*
    for(int i=0;i<n;i++) cout<<posj[i]<<" ";
        cout<<endl;
    for(int i=0;i<n;i++) cout<<poso[i]<<" ";
        cout<<endl;
    for(int i=0;i<n;i++) cout<<posi[i]<<" ";
        cout<<endl; */

    if(J<k || O<k || I<k){
        cout<<"-1"<<endl; return;
    }

    vector<int> js(J-k+1), os(O-k+1), is(I-k+1);

    vector<int> je(J-k+1), oe(O-k+1), ie(I-k+1);

    for(int i=0;i<J-k+1;i++){
        js[i]=posj[i];
        je[i]=posj[i+k-1];
    }
    for(int i=0;i<O-k+1;i++){
        os[i]=poso[i];
        oe[i]=poso[i+k-1];
        //cout<<os[i]<<" "<<oe[i]<<endl;
    }
    for(int i=0;i<I-k+1;i++){
        is[i]=posi[i];
        ie[i]=posi[i+k-1];
        //cout<<is[i]<<" "<<ie[i]<<endl;
    }

    int mn=INF;

    for(int i=0;i<J-k+1;i++){
        auto oloc=upper_bound(os.begin(),os.end(),je[i])-os.begin();
        if(oloc>=O-k+1) break;
        auto iloc=upper_bound(is.begin(),is.end(),oe[oloc])-is.begin();
        if(iloc>=I-k+1) break;

        int len=ie[iloc]-js[i]+1;
        mn=min(mn,len);
    }
    int ans=mn-(3*k);
    if(ans>=INF/2) cout<<"-1"<<endl;
    else cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    //freopen("hps.in", "r", stdin); freopen("hps.out", "w", stdout);
    int T=1; //cin>>T;
    while (T--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...