Submission #657376

#	Time	Username	Problem	Language	Result	Execution time	Memory
657376		inwbear	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	13 ms	1784 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
vector<int>v[3];
int n,k;
string s;
int main(){
    cin>>n>>k;
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='J'){
            v[0].push_back(i);
        }else if(s[i]=='O'){
            v[1].push_back(i);
        }else{
            v[2].push_back(i);
        }
    }
    int min=INT_MAX;
    for(int i=k-1;i<v[0].size();i++){
        int comp=v[0][i];
        int x=-1;
        //printf("[j:%d]",comp);
        int st=0,en=v[1].size()-1;
        while(st<=en){
          //printf("-%d-",comp);
            int mid=(st+en)/2;
            if(v[1][mid]>comp){
              //printf("[=%d %d=]",v[1][mid],comp);
                en=mid-1;
                x=mid;
            }else{
                st=mid+1;
            }
        }
        if(x==-1){
            break;
        }
        x+=k-1;
        if(x>=v[1].size()){
            break;
        }
        int y=0;
        comp=v[1][x];
        //printf("[O:%d]",comp);
        st=0,en=v[2].size()-1;
        while(st<=en){
            int mid=(st+en)/2;
            if(v[2][mid]>comp){
                en=mid-1;
                x=mid;
                y=1;
            }else{
                st=mid+1;
            }
        }
        if(y!=1){
            break;
        }
        x+=k-1;
        if(x>=v[2].size()){
            break;
        }
        int ans=v[2][x]-(v[0][i-k+1])+1-3*k;
        if(ans<min){
            //cout<<v[2][x]<<" "<<(v[0][i-k+1])<<endl;
            min=ans;
        }
    }
    if(min!=INT_MAX){
        cout<<min;
    }else{
        cout<<"-1";
    }
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=k-1;i<v[0].size();i++){
      |                   ~^~~~~~~~~~~~
ho_t2.cpp:39:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if(x>=v[1].size()){
      |            ~^~~~~~~~~~~~~
ho_t2.cpp:60:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if(x>=v[2].size()){
      |            ~^~~~~~~~~~~~~

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