Submission #979885

#	Time	Username	Problem	Language	Result	Execution time	Memory
979885		IUA_Hasin	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	96 ms	21276 KiB

ho_t2

#include <bits/stdc++.h>

#define ll                                  long long
#define ld                                  long double
#define endl                                "\n"

using namespace std;


int main(){
    #if __has_include("LOCAL.hh")
        #include "LOCAL.hh"
    #endif

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif



    ll n, k;
    cin>>n>>k;
    string s;
    cin>>s;

    vector<ll> vj, vo, vi;
    for(int i=0; i<n; i++){
        if(s[i]=='J'){
            vj.push_back(i);
        } else if(s[i]=='O'){
            vo.push_back(i);
        } else if(s[i]=='I'){
            vi.push_back(i);
        }
    }

    map<ll, ll> mj, mo, mi;
    for(int i=0; i<vj.size(); i++){
        ll a = vj[i];
        if(i<=(vj.size()-k)){
            ll b = vj[i+k-1];
            mj[a] = b; 
        } else {
            mj[a] = -1;
        }
    }

    set<ll> so;
    for(int i=0; i<vo.size(); i++){
        ll a = vo[i];
        if(i<=(vo.size()-k)){
            ll b = vo[i+k-1];
            mo[a] = b;
        } else {
            mo[a] = -1;
        }
        so.insert(a);
    }

    set<ll> si;
    for(int i=0; i<vi.size(); i++){
        ll a = vi[i];
        if(i<=(vi.size()-k)){
            ll b = vi[i+k-1];
            mi[a] = b;
        } else {
            mi[a] = -1;
        }
        si.insert(a);
    }


    // for(int i=0; i<vj.size(); i++){
    //     cout << mj[vj[i]] << " ";
    // }
    // cout<<endl;
    // for(int i=0; i<vo.size(); i++){
    //     cout << mo[vo[i]] << " ";
    // }
    // cout<<endl;
    // for(int i=0; i<vi.size(); i++){
    //     cout << mi[vi[i]] << " ";
    // }
    // cout<<endl;
    // cout<<endl;

    // for(auto u : so){
    //     cout << u << " ";
    // }
    // cout<<endl;
    // for(auto u : si){
    //     cout << u << " ";
    // }
    // cout<<endl;
    // cout<<endl;

    ll status = -1;
    ll possible = 1;
    ll ans = 1e9;

    for(int i=0; i<=vj.size()-k; i++){
        if(possible==-1){
            break;
        } else {
            ll a = vj[i];
            ll b = mj[a];
            //cout << a << " " << b << endl;
            auto it = so.upper_bound(b);
            ll temp1;
            if(it==so.end()){
                possible=-1;
                break;
            } else {
                temp1 = *it;
            }
            ll c = mo[temp1];
            //cout << c << " " << temp1 << endl;
            if(c==-1){
                possible = -1;
                break;
            } else {
                auto it2 = si.upper_bound(c);
                ll temp2;
                if(it2==si.end()){
                    possible = -1;
                    break;
                } else {
                    temp2 = *it2;
                }
                ll d = mi[temp2];
                //cout << d << " " << temp2 << endl;
                if(d==-1){
                    possible = -1;
                    break;
                } else {
                    status = 1;
                    ll e = d-a+1;
                    ll tempans = e-3*k;
                    ans = min(ans, tempans);
                    //cout << e << " " << tempans << endl;
                }
            }
        }
    }

    //cout << status << endl;
    if(status==1){
        cout << ans << endl;
    } else {
        cout << -1 << endl;
    }
    






    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (ld)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif


    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0; i<vj.size(); i++){
      |                  ~^~~~~~~~~~
ho_t2.cpp:48:13: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   48 |         if(i<=(vj.size()-k)){
      |            ~^~~~~~~~~~~~~~~
ho_t2.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0; i<vo.size(); i++){
      |                  ~^~~~~~~~~~
ho_t2.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   59 |         if(i<=(vo.size()-k)){
      |            ~^~~~~~~~~~~~~~~
ho_t2.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0; i<vi.size(); i++){
      |                  ~^~~~~~~~~~
ho_t2.cpp:71:13: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   71 |         if(i<=(vi.size()-k)){
      |            ~^~~~~~~~~~~~~~~
ho_t2.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  109 |     for(int i=0; i<=vj.size()-k; i++){
      |                  ~^~~~~~~~~~~~~

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