Submission #474685

#	Time	Username	Problem	Language	Result	Execution time	Memory
474685		tonychi123	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	13 ms	3308 KiB

ho_t2

#define cerr cout
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target("avx,avx2,tune=native")
#include <bits/stdc++.h>

#define endl '\n'
#define all(v) begin(v), end(v)
#define ub upper_bound
#define lb lower_bound

// DBN is defined in /usr/local/Cellar/gcc/11.2.0/include/c++/11.2.0/x86_64-apple-darwin20/bits/stdc++.h
#ifndef tony 
#define DBN(...)
#define DBN1D(...) 
#define DBN2D(...) 
#define dbn(...)
#endif

template<typename T>
using Prior=std::priority_queue<T>;
template<typename T>
using prior=std::priority_queue<T,std::vector<T>,std::greater<T>>;

using namespace std;
typedef long long loli;
typedef vector<loli> vl;
typedef vector<vl> vvl;
typedef pair<loli,loli> pll;
typedef pair<pll,pll> pllll;
typedef vector<pll> vpll;
typedef long double ld;
typedef vector<ld> vld;
typedef vector<bool> vb;
const loli md=1e9+7;

inline loli mod(loli x){
    return (x%md+md)%md;
}

void solve(){
    int n,k;
    cin>>n>>k;
    string str;
    cin>>str;
    vl J,O,I;
    for(int i=0;i<n;++i)
        if(str[i]=='J')
            J.push_back(i);
        else if(str[i]=='O')
            O.push_back(i);
        else
            I.push_back(i);
    DBN(J,O,I);
    loli ans=1e9;
    for(int i=0;i+k-1<J.size();++i){
        dbn(J[i+k-1]);
        auto oit=lb(all(O),J[i+k-1]);
        dbn(*oit)
        if(O.end()-oit<k)
            break;
        dbn(*(oit+k-1))
        auto iit=lb(all(I),*(oit+k-1)+1);
        if(I.end()-iit<k)
            break;
        dbn(*(iit+k-1),J[i],k*3)
        ans=min(ans,*(iit+k-1)-J[i]-k*3+1);
        dbn(ans)
        dbn("            ")
    }
    cout<<(ans==1e9?-1:ans)<<endl;


}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int _=1;
    // cin>>_;
    vl __(_);
    iota(all(__),1);
    for(auto i:__){
        #ifndef tony
        //cout<<"Case #"<<i<<": ";
        #endif
        solve();
        #ifdef tony
        // break;
        cerr<<"=================================================\n";
        #endif
    }
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'void solve()':
ho_t2.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i+k-1<J.size();++i){
      |                 ~~~~~^~~~~~~~~
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:84:14: warning: unused variable 'i' [-Wunused-variable]
   84 |     for(auto i:__){
      |              ^

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