Submission #1349302

#TimeUsernameProblemLanguageResultExecution timeMemory
1349302makskusJJOOII 2 (JOI20_ho_t2)C++20
0 / 100
0 ms344 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <climits>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <functional>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0;a<b;a++)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
const int inf = 1e9;
const ll infl = 1e18;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<int> pref_o(n);
    vector<int> pref_i(n);
    vector<int> poz_j;

    rep(i, n){
        if(s[i] == 'J'){
            poz_j.pb(i);
        }
    }

    rep(i, n){
        if(i == 0){
            if(s[0] == 'O'){
                pref_o[0] = 1;
            }
            else if(s[0] == 'I'){
                pref_i[0] = 1;
            }
        }
        else{
            if(s[i] == 'O'){
                pref_o[i] = pref_o[i-1]+1;
            }
            else{
                pref_o[i] = pref_o[i-1];
            }

            if(s[i] == 'I'){
                pref_i[i] = pref_i[i-1]+1;
            }
            else{
                pref_i[i] = pref_i[i-1];
            }
        }
    }

    if(poz_j.size() < k){
        cout << -1 << "\n";
        return 0;
    }

    int w = inf;

    for(int kon = k-1; kon < poz_j.size(); kon++){
        int akt = 0;
        int poc = kon - (k-1);
        int ost_o_liczba;
        auto ost_o = lower_bound(pref_o.begin(), pref_o.end(), pref_o[kon]+k);

        if(ost_o == pref_o.end()){
            continue;
        }
        else{
            ost_o_liczba = ost_o - pref_o.begin();
        }
        //cout << pref_o[kon]+k << "\n";
        //cout << ost_o_liczba << "\n";

        auto ost_i = lower_bound(pref_i.begin(), pref_i.end(), pref_i[ost_o_liczba]+k);
        if(ost_i == pref_i.end()){
            continue;
        }
        else{
            int ost_i_liczba = ost_i - pref_i.begin();
            w = min(w, ost_i_liczba-poc+1 - 3*k);
            //cout << ost_i_liczba << "\n";
        }
        
    }

    if(w != inf){
        cout << w << "\n";
    }
    else{
        cout << -1 << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...