Submission #1155054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155054		Roman70	JJOOII 2 (JOI20_ho_t2)	C++20	13 / 100	2093 ms	1792 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

int find_pos(const vector<int>& v, int pos, int k) {
    auto it = lower_bound(v.begin(), v.end(), pos);  // Binary search for lower bound
    int cnt = 0;
    
    if (it != v.end()) cnt++;  // if there is at least one element greater than or equal to pos
    
    while (it != v.end() && cnt != k) {
        cnt++;
        it++;
    }
    
    if (cnt == k && it != v.end()) return *it;
    else return -1;
}

int main() {
    int n, k;
    cin >> n >> k;
    string a;
    cin >> a;

    vector<int> b[3];  // Using vectors for 'J', 'O', and 'B' positions
    
    // Store positions of J, O, and B
    for (int i = 0; i < n; i++) {
        if (a[i] == 'J') b[0].push_back(i);
        else if (a[i] == 'O') b[1].push_back(i);
        else b[2].push_back(i);
    }

    // Sort the vectors for binary search
    for (int i = 0; i < 3; i++) {
        sort(b[i].begin(), b[i].end());
    }

    int mnm = 1e9;

    // Try to find the smallest sequence of 'J', 'O', 'B'
    for (int i = 0; i < n; i++) {
        if (a[i] == 'J') {
            int pos1 = find_pos(b[0], i, k);
            if (pos1 != -1) {
                int pos2 = find_pos(b[1], pos1, k);
                if (pos2 != -1) {
                    int pos3 = find_pos(b[2], pos2, k);
                    if (pos3 != -1) {
                        int loc = pos3 - i + 1;
                        int cr = 3 * k;
                        if (loc > 0 && cr > 0 && loc - cr >= 0) {
                            mnm = min(mnm, loc - cr);
                        }
                    }
                }
            }
        }
    }

    // Output result
    if (mnm != 1e9) {
        cout << mnm;
    } else {
        cout << -1;
    }

    return 0;
}

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