Submission #1322301

#TimeUsernameProblemLanguageResultExecution timeMemory
1322301mantaggezJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
10 ms1796 KiB
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

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

int Bsearch(int idx, vector<int>& v)
{
    int l = 0, r = v.size() - 1;
    int result = -1;
    
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(v[mid] > idx) {
            result = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return result;
}

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++)
    {
        int end_J = i;
        int start_J = i - k + 1;

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

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

        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...