Submission #1155057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155057		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);  
    int idx = distance(v.begin(), it);  
    

    if (idx + k - 1 < v.size()) {
        return v[idx + k - 1]; 
    } else {
        return -1;  
    }
}

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

    vector<int> b[3];  
    
  
    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);
    }


    for (int i = 0; i < 3; i++) {
        sort(b[i].begin(), b[i].end());
    }

    int mnm = 1e9;


    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);
                        }
                    }
                }
            }
        }
    }

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

    return 0;
}

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