Submission #1118652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118652		secretwood01	JJOOII 2 (JOI20_ho_t2)	C++17	13 / 100	1071 ms	9948 KiB

ho_t2

#include <iostream>
#include <set>
#include <string>
#include <sstream>
#include <limits>

using namespace std;

class Jjooii {
public:
    static void main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int N, K;
        cin >> N >> K;
        set<int> Js, Is, Os;
        string S;
        cin >> S;

        for (int i = 0; i < N; i++) {
            char c = S[i];
            if (c == 'J') Js.insert(i);
            else if (c == 'I') Is.insert(i);
            else Os.insert(i);
        }

        int ans = numeric_limits<int>::max();
        int iterations = 0;

        if (!Js.empty()) {
            int right = -1;
            int left = *Js.begin();
            Js.erase(Js.begin());
            int nLeft = next(Js, K - 1, left);
            if (nLeft >= 0) {
                int nnLeft = next(Os, K, nLeft);
                if (nnLeft > 0) {
                    right = next(Is, K, nnLeft);
                }
            }
            if (right > 0) ans = min(ans, right - left + 1 - (3 * K));
            while (right > 0 && !Js.empty() && iterations < 50000) {
                left = *Js.begin();
                Js.erase(Js.begin());
                right = -1;
                int nL = next(Js, K - 1, left);
                if (nL >= 0) {
                    int nnL = next(Os, K, nL);
                    if (nnL > 0) {
                        right = next(Is, K, nnL);
                    }
                }
                if (right > 0) ans = min(ans, right - left + 1 - (3 * K));
                iterations++;
            }
        }
        if (ans == numeric_limits<int>::max()) ans = -1;
        cout << ans << endl;
    }

    static int next(set<int>& s, int n, int curr) {
        int counter = min(n, 1000);
        int toReturn = curr;
        auto it = s.upper_bound(toReturn);
        while (counter > 0 && it != s.end()) {
            toReturn = *it;
            it++;
            counter--;
        }
        if (counter > 0) return -1;
        return toReturn;
    }
};

int main() {
    Jjooii::main();
    return 0;
}

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