Submission #940889

#	Time	Username	Problem	Language	Result	Execution time	Memory
940889		LittleOrange	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	12 ms	3448 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k;
    string s;
    cin >> n >> k >> s;
    {
        ll c0=0,c1=0,c2=0;
        for(char c : s){
            if(c=='J')c0++;
            if(c0>=k&&c=='O')c1++;
            if(c1>=k&&c=='I')c2++;
        }
        if(c2<k){
            cout << "-1\n";
            return 0;
        }
    }
    vector<ll> a,b,c;
    for(ll i = 0;i<n;i++){
        if(s[i]=='J') a.push_back(i);
        if(s[i]=='O') b.push_back(i);
        if(s[i]=='I') c.push_back(i);
    }
    //for(ll i = 0 ;i<a.size();i++) cout << a[i] << " \n"[i+1==a.size()];
    //for(ll i = 0 ;i<b.size();i++) cout << b[i] << " \n"[i+1==b.size()];
    //for(ll i = 0 ;i<c.size();i++) cout << c[i] << " \n"[i+1==c.size()];
    ll ans = 1e18;
    for(ll i = 0;i+k<=a.size();i++){
        ll L = a[i];
        ll p0 = a[i+k-1];
        //cout << "L=" << L << ", p0=" << p0 << "\n";
        auto P1 = upper_bound(b.begin(),b.end(),p0);
        if(P1==b.end()) continue;
        ll p1 = P1-b.begin();
        //cout << "p1=" << p1 << "\n";
        if(p1+k>b.size()) continue;
        ll p2 = b[p1+k-1];
        //cout << "p2=" << p2 << "\n";
        auto P3 = upper_bound(c.begin(),c.end(),p2);
        if(P3==c.end()) continue;
        ll p3 = P3-c.begin();
        if(p3+k>c.size()) continue;
        ll R = c[p3+k-1];
        //cout << L << "~" << R << "\n";
        ans = min(ans,R-L+1-k*3);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:31:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(ll i = 0;i+k<=a.size();i++){
      |                  ~~~^~~~~~~~~~
ho_t2.cpp:39:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if(p1+k>b.size()) continue;
      |            ~~~~^~~~~~~~~
ho_t2.cpp:45:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if(p3+k>c.size()) continue;
      |            ~~~~^~~~~~~~~

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