Submission #1322282

#TimeUsernameProblemLanguageResultExecution timeMemory
1322282mantaggezJJOOII 2 (JOI20_ho_t2)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int n, k;
string s;
vector<int> J, O, I;

bool check(int mid, int idx, vector<int>& v) { return v[mid] > idx; }

int Bsearch(int l, int r, vector<int>& v, int idx)
{
    while(l < r)
    {
        int mid = (l + r) / 2;
        bool ok = check(mid, idx, v);
        if(ok) r = mid;
        else l = mid + 1;
    }
    // cout << "Bsearch : " << l << '\n';
    return l;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> k >> s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i] == 'J')
            J.push_back(i);
        if(s[i] == 'O')
            O.push_back(i);
        if(s[i] == 'I')
            I.push_back(i);
    }
    // for(int i=0;i<n;i++) cout << i; cout << '\n';

    int res = INF;
    for(int i=k-1;i<J.size();i++)
    {
        if(O.size() <= 0 || I.size() <= 0) continue;
        int end_J = i;
        int start_J = i - k + 1;

        int start_O = Bsearch(0, O.size() - 1, O, J[end_J]);
        int end_O = start_O + k - 1;

        int start_I = Bsearch(0, I.size() - 1, I, O[end_O]);
        int end_I = start_I + k - 1;

        if(O[start_O] < J[end_J] || I[start_I] < O[end_O] || end_O < start_O || end_I < start_I) continue;

        // cout << "J : " << J[end_J] << ' ' << J[start_J] << '\n';
        // cout << "O : " << O[end_O] << ' ' << O[start_O] << '\n';
        // cout << "I : " << I[end_I] << ' ' << I[start_I] << '\n';
        // cout << '\n';

        int sum = ((I[end_I] - J[start_J] + 1) - (3 * k)) ;

        res = min(res, sum);
    }

    cout << (res == INF ? -1 : res);

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...