Submission #541538

#	Time	Username	Problem	Language	Result	Execution time	Memory
541538		NyanCatTW1	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	328 KiB

ho_t2

#include <iostream>
#include <vector>
#include <deque>

using namespace std;
typedef long long LL;

#define rangeLen(x) (partRange[x].second - partRange[x].first)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    string SStr;
    cin >> N >> K >> SStr;

    vector<int> S(SStr.size());
    vector<vector<int> > charIndexes(3);
    for (int i = 0; i < SStr.size(); i++) {
        switch (SStr[i]) {
            case 'J':
                S[i] = 0;
                charIndexes[0].push_back(i);
                break;
            case 'O':
                S[i] = 1;
                charIndexes[1].push_back(i);
                break;
            case 'I':
                S[i] = 2;
                charIndexes[2].push_back(i);
                break;
        }
    }
 
    int ans = 1000000;
    vector<pair<int, int> > partRange(3);
    vector<int> partEndIndex(3);
    int R = -1;
    for (int L = 0; L < S.size(); L++) {
        if (L) {
            int toRemove = S[L - 1];
            if (rangeLen(toRemove) != 0 && charIndexes[toRemove][partRange[toRemove].first] == L - 1) {
                partRange[toRemove].first++;
                if (rangeLen(toRemove) >= K) {
                    partEndIndex[toRemove] = charIndexes[toRemove][partRange[toRemove].first + K - 1];
                }
            }
        }

        for (int k = 0; k < 3; k++) {
            if (k) {
                while (rangeLen(k) != 0 && charIndexes[k][partRange[k].first] < partEndIndex[k - 1]) {
                    partRange[k].first++;
                }
            }

            while (R + 1 != S.size() && rangeLen(k) < K) {
                R++;
                partRange[S[R]].second++;
                if (rangeLen(S[R]) == K) {
                    partEndIndex[S[R]] = charIndexes[S[R]][partRange[S[R]].second - 1];
                }
            }

            if (rangeLen(k) < K) {
                goto end;
            }
        }

        ans = min(ans, (R - L + 1) - K * 3);
    }

    end:
    if (ans == 1000000) ans = -1;
    cout << ans << '\n';
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < SStr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
ho_t2.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int L = 0; L < S.size(); L++) {
      |                     ~~^~~~~~~~~~
ho_t2.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             while (R + 1 != S.size() && rangeLen(k) < K) {
      |                    ~~~~~~^~~~~~~~~~~

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