제출 #1155056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155056		Roman70	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	18 ms	1748 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 idx = distance(v.begin(), it);  // Get the index of the iterator in the vector
    
    // Check if there is a valid k-th element after `pos`
    if (idx + k - 1 < v.size()) {
        return v[idx + k - 1];  // Return the k-th element after pos (0-based index)
    } else {
        return -1;  // No such element exists
    }
}

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: 87 / 87