Submission #1101826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101826		BlueGlaucus1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	24 ms	3428 KiB

ho_t2

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int n; 
 
int find(int target, int low, vector<int> &arr) {
    int high = n;
    int val = -1;
    int mid;
 
    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] >= target) {
            val = mid;
            high = mid - 1;
        } 
        else if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    return val;
}

int main() {
    string s;
    int k;
    cin >> n;
    cin >> k;
    cin >> s;
 
    vector<int> prefixj ;
    vector<int> prefixo;
    vector<int> prefixi;
    prefixj.push_back(0);
    prefixi.push_back(0);
    prefixo.push_back(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++;
        }
        prefixj.push_back(jCount);
        prefixo.push_back(oCount);
        prefixi.push_back(iCount); 
    }
    int answer = 200001;
 
    for (int i = 1; i <=n; i++) {
        int position_of_j = find(prefixj[i-1] + k, i, prefixj);
        if (position_of_j == -1) {
            break;
        }
        int position_of_o = find(prefixo[position_of_j] + k, position_of_j, prefixo);
        if (position_of_o == -1) {
            break;
        }

        int position_of_i = find(prefixi[position_of_o] + k, position_of_o, prefixi);
        if (position_of_i == -1) {
            break;
        }
        answer = min(answer, position_of_i - i - 3 * k + 1);
    }
    if (answer == 200001) {
        answer = -1;
    }
    cout << answer;
}

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