Submission #1223348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223348		overwatch9	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	90 ms	2064 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
map <char, vector <int>> pos;
int n, k;
bool check(int st, int ed) {
    auto it = lower_bound(pos['J'].begin(), pos['J'].end(), st) - pos['J'].begin();
    it += k - 1;
    if (it >= (int)pos['J'].size())
        return false;
    int p = pos['J'][it];
    it = lower_bound(pos['O'].begin(), pos['O'].end(), p) - pos['O'].begin();
    it += k - 1;
    if (it >= (int)pos['O'].size())
        return false;
    p = pos['O'][it];
    it = lower_bound(pos['I'].begin(), pos['I'].end(), p) - pos['I'].begin();
    it += k - 1;
    if (it >= (int)pos['I'].size())
        return false;
    return pos['I'][it] <= ed;
}
int main() {
    cin >> n >> k;
    string s;
    cin >> s;
    s = "0" + s;
    for (int i = 1; i <= n; i++) {
        pos[s[i]].push_back(i);
    }
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        if (s[i] != 'J')
            continue;
        int lo = i, hi = n+1;
        int j, o, I;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (check(i, mid))
                hi = mid;
            else
                lo = mid + 1;
        }
        if (check(i, hi)) {
            if (ans == -1)
                ans = n - k;
            ans = min(ans, (hi - i + 1) - (3 * k));
        }
    }
    cout << ans << '\n';



}

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