Submission #1089083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089083		Izzy	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	28 ms	3316 KiB

ho_t2

#include <iostream>
#include <string>
#include <vector>
// #include <unordered_map>
using namespace std;

string s;
int n; 
int k;

int find(int target, int low, vector<int> &arr) {
    int high = n;
    int working = -1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] >= target) {
            working = mid;
            high = mid - 1;
        } 
        else if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    return working;
}

int main() {
    cin >> n;
    cin >> k;
    cin >> s;

    vector<int> jPref = {0};
    vector<int> oPref = {0};
    vector<int> iPref = {0};

    int jCount = 0;
    int oCount = 0;
    int iCount = 0;
    for (auto p: s) {
        if (p == 'J') {
            jCount++;
        }
        else if (p == 'O') {
            oCount++;
        }
        else if (p == 'I') {
            iCount++;
        }
        jPref.push_back(jCount);
        oPref.push_back(oCount);
        iPref.push_back(iCount); 
    }

    int counter = 200001;

    for (int p = 1; p < n + 1; p++) {
        int jPos = find(jPref[p - 1] + k, p, jPref);
        // cout << jPos << ' ';
        if (jPos == -1) {
            break;
        }
        int oPos = find(oPref[jPos] + k, jPos, oPref);
        // cout << oPos << ' ';
        if (oPos == -1) {
            break;
        }
        int iPos = find(iPref[oPos] + k, oPos, iPref);
        // cout << iPos << ' ';
        if (iPos == -1) {
            break;
        }
        // cout << counter << endl;
        counter = min(counter, iPos - p - 3 * k + 1);
    }
    if (counter == 200001) {
        counter = -1;
    }
    cout << counter;
}

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