제출 #1279759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279759		yassia	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	9 ms	2664 KiB

ho_t2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using hash_map = gp_hash_table<int, int>;
using hash_set = gp_hash_table<int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
using ord_set = tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
const ll inf = 1e18;

void solve1() {
    ll n, k;
    cin >> n >> k;
    str s;
    cin >> s;
    str need;
    for(int j = 0; j < k; j++){
        need.push_back('J');
    }
    for (int j =0; j< k; j++){
        need.push_back('O');
    }
    for(int j =0; j< k; j++){
        need.push_back('I');
    }
    deque<char> s1;
    for(auto x: s)s1.emplace_back(x);
    while (!s1.empty()&& (s1.front()!='J' || s1.back()!='I')){
        if (s1.front()!='J'){
            s1.pop_front();
        }
        if (!s1.empty()&& s1.back()!='I'){
            s1.pop_back();
        }
        if (s1.size()<need.size()){
            cout<<-1<<endl;
            return;
        }
    }

    s ="";
    for(auto u : s1)s.push_back(u);
    n = s.size();
    deque<ll> Js;
    deque<ll> Os;
    deque<ll> Is;
    for (int i=0; i<n ;i++){
        if (s[i]=='J'){
            Js.push_back(i);
        }
        else if (s[i]=='O'){
            Os.push_back(i);
        }
        else Is.push_back(i);
    }
    if (Js.size()<k||Os.size()<k||Is.size()<k){
        cout<<-1<<endl;
        return;
    }
    ll mn_ans = inf;
    for (int j = k-1; j < Js.size(); j++){
        ll cur_j = Js[j];
        ll pre_j = Js[j-k+1];
        while (!Os.empty()&&Os.front()<cur_j){
            Os.pop_front();
        }
        while (!Is.empty()&&Is.front()<cur_j){
            Is.pop_front();
        }
        if(Is.size()<k||Os.size()<k){
            break;
        }
        ll ans = (cur_j - pre_j+1) - k;
        ll pre_o = Os.front();
        ans += (pre_o-cur_j-1);
        ll cur_o = Os[k-1];
        ll nx_it = upper_bound(Is.begin(), Is.end(), cur_o)-Is.begin();
        if (nx_it+k-1 >= Is.size()){
            break;
        }
        ll pre_i = Is[nx_it];
        ll cur_i = Is[nx_it+k-1];
        ans += (cur_o - pre_o+1) - k;
        ans += (pre_i-cur_o-1);
        ans += (cur_i-pre_i+1)-k;
        mn_ans=min(mn_ans, ans);
    }
    if (mn_ans == inf){
        cout<<-1<<endl;
    }
    else cout << mn_ans<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t1 = 1;
    //  cin>>t1;
    for (int o_ = 0; o_ < t1; o_++) {
        solve1();
    }
#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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