Submission #386076

#	Time	Username	Problem	Language	Result	Execution time	Memory
386076		strawberry2005	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	364 KiB

ho_t2

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 1e9+7;
#define deb(x) cout<<#x<<": "<<x<<endl

int iceil(int a, int b) {
  return (a + b - 1) / b;
}
signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(20);

    #ifdef strawberryshaker2005
        freopen("input.txt", "r", stdin);
    #endif

    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    vector<int> js,os,is,fj,fo,fi;
    for(int i=0;i<n;i++){
        if(s[i]=='J') js.push_back(i);
        if(s[i]=='O') os.push_back(i);
        if(s[i]=='I') is.push_back(i);
    }

    fj.push_back(0);
    for(int i=1;i<js.size();i++){
        fj.push_back(fj[i-1]+(js[i]-js[i-1]-1));
    }
    fo.push_back(0);
    for(int i=1;i<os.size();i++){
        fo.push_back(fo[i-1]+(os[i]-os[i-1]-1));
    }
    fi.push_back(0);
    for(int i=1;i<is.size();i++){
        fi.push_back(fi[i-1]+(is[i]-is[i-1]-1));
    }
    int ans=mod;
    for(int i=0;i<fj.size();i++){
        int temp=0;
        int ostart=mod,istart=mod;
        if(i+k-1<fj.size()){
            ostart=js[i+k-1]+1;
            temp+=fj[i+k-1]-fj[i];
        }
        else break;
        if(ostart+k-1<n){
            int real_ostart=0;
            if(lower_bound(os.begin(),os.end(),ostart)==os.end()) break;
            else real_ostart=distance(os.begin(),lower_bound(os.begin(),os.end(),ostart));
            //deb(real_ostart);
            temp+=fo[real_ostart+k-1]-fo[real_ostart];
            istart=os[real_ostart+k-1]+1;
        }
        else break;
        //deb(temp);
        if(istart+k-1<n){
            int real_istart=0;
            if(lower_bound(is.begin(),is.end(),istart)==is.end()) break;
            else real_istart=distance(is.begin(),lower_bound(is.begin(),is.end(),istart));
            temp+=fi[real_istart+k-1]-fi[real_istart];
        }
        else break;
        ans=min(ans,temp);
    }
    if(ans==mod) cout<<"-1\n";
    else cout<<ans<<endl;



    return(0);
    
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:34:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=1;i<js.size();i++){
      |                 ~^~~~~~~~~~
ho_t2.cpp:38:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i=1;i<os.size();i++){
      |                 ~^~~~~~~~~~
ho_t2.cpp:42:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=1;i<is.size();i++){
      |                 ~^~~~~~~~~~
ho_t2.cpp:46:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<fj.size();i++){
      |                 ~^~~~~~~~~~
ho_t2.cpp:49:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if(i+k-1<fj.size()){
      |            ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87