oj.uz

Submission #541538

# Submission time Handle Problem Language Result Execution time Memory
541538 2022-03-23T18:06:45 Z NyanCatTW1 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 328 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -