Submission #1343228

#TimeUsernameProblemLanguageResultExecution timeMemory
1343228jmuzhenJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
18 ms5888 KiB
#include<bits/stdc++.h>
using namespace std;

#define DEBUG 0
#define printf if(DEBUG) printf

constexpr int MAXN = 2e5+10;

int to_int(char c) {
    //j,o,i
    if (c=='J')return 0;
    if (c=='O')return 1;
    if (c=='I') return 2;
    assert(false);
}

vector<vector<int>> pref(3, vector<int>(MAXN)), suff(3, vector<int>(MAXN)); // 0
vector<int> total_count(3,0);

int main() {
    int n,k;cin>>n>>k;
    string s;cin>>s;
    for (int i = 1; i <= n; i++) {
        int ch = to_int(s[i-1]);
        total_count[ch]++;
        for (int c = 0; c < 3; c++) {
            pref[c][i] = pref[c][i-1];
            if (ch == c) pref[c][i]++;
        }
    }
    for (int i = n; i >= 1; i--) {
        int ch = to_int(s[i-1]);
        for (int c = 0; c < 3; c++) {
            suff[c][i] = suff[c][i+1];
            if (ch == c) suff[c][i]++;
        }
    }

    int ans = 1e9;

    auto find_next = [&](int i, int c) {
        int pref_begin = pref[c][i-1];
        // look for first i that is at least pref_begin + k
        int l = i, r = n;
        int best = -1;
        while (l <= r) {
            int mid = l+(r-l)/2;
            bool ok = (pref[c][mid] >= pref_begin + k);
            if (ok) {
                best = mid;
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return best;
    };

    for (int idx_start = 1; idx_start <= n; idx_start++) {
        printf("idx_start %d\n", idx_start);
        int ch = to_int(s[idx_start-1]);
        if (ch != 0) continue;

        int idx_j = find_next(idx_start, 0);
        printf("idx_j %d\n", idx_j);
        if (idx_j == -1) continue;

        int idx_o = find_next(idx_j+1, 1);
        printf("idx_o %d\n", idx_o);
        if (idx_o == -1) continue;

        int idx_i = find_next(idx_o+1, 2);
        printf("idx_i %d\n", idx_i);
        if (idx_i == -1) continue;

        int this_ans = (idx_i - idx_start+1) - 3 * k;

        ans = min(ans, this_ans);

    }

    if (ans==1e9)ans=-1;
    cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...