oj.uz

Submission #541517

# Submission time Handle Problem Language Result Execution time Memory
541517 2022-03-23T17:38:48 Z NyanCatTW1 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 212 KB 
#include <iostream>
#include <vector>
#include <deque>

using namespace std;
typedef long long LL;

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

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

    vector<int> S(SStr.size());
    for (int i = 0; i < SStr.size(); i++) {
        switch (SStr[i]) {
            case 'J':
                S[i] = 0;
                break;
            case 'O':
                S[i] = 1;
                break;
            case 'I':
                S[i] = 2;
                break;
        }
    }
 
    int ans = 1000000;
    vector<deque<int> > usefulChars(3);
    vector<int> partEndIndex(3);
    int R = -1;
    for (int L = 0; L < S.size(); L++) {
        if (L) {
            int toRemove = S[L - 1];
            if (usefulChars[toRemove].size() && usefulChars[toRemove].front() == L - 1) {
                usefulChars[toRemove].pop_front();
            }
        }

        for (int k = 0; k < 3; k++) {
            if (k) {
                while (usefulChars[k].size() && usefulChars[k].front() < partEndIndex[k - 1]) {
                    usefulChars[k].pop_front();
                }
            }

            while (R + 1 != S.size() && usefulChars[k].size() < K) {
                R++;
                usefulChars[S[R]].push_back(R);
                if (usefulChars[S[R]].size() == K) {
                    partEndIndex[S[R]] = usefulChars[S[R]].back();
                }
            }

            if (usefulChars[k].size() < 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:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < SStr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
ho_t2.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int L = 0; L < S.size(); L++) {
      |                     ~~^~~~~~~~~~
ho_t2.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             while (R + 1 != S.size() && usefulChars[k].size() < K) {
      |                    ~~~~~~^~~~~~~~~~~
ho_t2.cpp:50:63: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |             while (R + 1 != S.size() && usefulChars[k].size() < K) {
      |                                         ~~~~~~~~~~~~~~~~~~~~~~^~~
ho_t2.cpp:53:46: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |                 if (usefulChars[S[R]].size() == K) {
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
ho_t2.cpp:58:39: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |             if (usefulChars[k].size() < K) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -