Submission #1122750

#TimeUsernameProblemLanguageResultExecution timeMemory
1122750SulAJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
8 ms1812 KiB
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n,k; cin >> n >> k;
    string s; cin >> s;
    vector<int> J, O, I;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'J') J.push_back(i);
        else if (s[i] == 'O') O.push_back(i);
        else I.push_back(i);
    }
    int ans = 1e9;
    for (int l = 0, r = k-1; r < O.size(); l++, r++) {
        int first = O[l];
        int cnt_J = lower_bound(all(J), first) - begin(J);
        if (cnt_J < k) continue;
        first = J[cnt_J - k];
        int last = O[r];
        int ind_I = upper_bound(all(I), last) - begin(I);
        if (ind_I + k-1 >= I.size()) continue;
        last = I[ind_I + k-1];
        ans = min(ans, last - first + 1 - 3*k);
    }
    cout << (ans == 1e9 ? -1 : ans);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...