Submission #753912

#	Time	Username	Problem	Language	Result	Execution time	Memory
753912		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	33 ms	3300 KiB

ho_t2

/*
isl gae
e
*/
#include <bits/stdc++.h>
#include <sstream>
#define ll                  long long
#define lp(a,b)             for(ll i = a; i<b; i++)
#define pl(a,b)             for(ll i = a;i>=b;i--)
using namespace std;
int main()
{  
    ll n,k;cin >> n >> k;string s;cin >> s;vector <ll> v[3];
    lp(0,n){
        v[(s[i] == 'J' ? 0 : (s[i] == 'O' ? 1 : 2))].push_back(i);
    }
    ll pt = 0,it = 0;
    string kx = string(k, 'J') + string(k, 'O') + string(k, 'I');
    while(pt < n && it < kx.size()){
        if(s[pt] == kx[it]){
            it++;
        }
        pt++;
    }
    if(it < k * 3){
        cout << -1 << char(012);exit(0);
    }
    ll mn = 1e9;
    lp(k * 3 - 1,n){
        if(v[0][0] > i || v[1][0] > i || v[2][0] > i){
            continue;
        }
        ll rx = --upper_bound(v[2].begin(), v[2].end(), i) - v[2].begin();
        ll lx = rx - k + 1;
        if(lx < 0){
            continue;
        }
        ll rxx = v[2][rx];
        ll lxx = v[2][lx];
        if(v[1][0] > lxx){
            continue;
        }
        ll rx2 = --upper_bound(v[1].begin(), v[1].end(), lxx) - v[1].begin();
        ll lx2 = rx2 - k + 1;
        if(lx2 < 0){
            continue;
        }
        ll rxx2 = v[1][rx2];
        ll lxx2 = v[1][lx2];
        if(v[0][0] > lxx2){
            continue;
        }
        ll rx3 = --upper_bound(v[0].begin(), v[0].end(), lxx2) - v[0].begin();
        ll lx3 = rx3 - k + 1;
        if(lx3 < 0){
            continue;
        }
        ll rxx3 = v[0][rx3];
        ll lxx3 = v[0][lx3];
        mn = min(mn, ((rxx - lxx3 + 1) - k * 3));
    }
    cout << mn << char(012);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:19:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while(pt < n && it < kx.size()){
      |                     ~~~^~~~~~~~~~~
ho_t2.cpp:48:12: warning: unused variable 'rxx2' [-Wunused-variable]
   48 |         ll rxx2 = v[1][rx2];
      |            ^~~~
ho_t2.cpp:58:12: warning: unused variable 'rxx3' [-Wunused-variable]
   58 |         ll rxx3 = v[0][rx3];
      |            ^~~~

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