oj.uz

Submission #541649

# Submission time Handle Problem Language Result Execution time Memory
541649 2022-03-24T01:14:07 Z NyanCatTW1 JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 9 ms 2852 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);
    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++;
            }
        }

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

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

            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:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int L = 0; L < S.size(); L++) {
      |                     ~~^~~~~~~~~~
ho_t2.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             while (R + 1 != S.size() && rangeLen(k) < K) {
      |                    ~~~~~~^~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 328 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 320 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 320 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 320 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 320 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 8 ms 2384 KB Output is correct
37 Correct 9 ms 2608 KB Output is correct
38 Correct 9 ms 2732 KB Output is correct
39 Correct 9 ms 2756 KB Output is correct
40 Correct 7 ms 2776 KB Output is correct
41 Correct 9 ms 2852 KB Output is correct
42 Correct 8 ms 2592 KB Output is correct
43 Correct 3 ms 1776 KB Output is correct
44 Correct 5 ms 2008 KB Output is correct
45 Correct 6 ms 2776 KB Output is correct
46 Correct 6 ms 2768 KB Output is correct
47 Correct 7 ms 2776 KB Output is correct
48 Correct 5 ms 2828 KB Output is correct
49 Correct 4 ms 1848 KB Output is correct
50 Correct 6 ms 2796 KB Output is correct
51 Correct 5 ms 2776 KB Output is correct
52 Correct 5 ms 2252 KB Output is correct
53 Correct 5 ms 2476 KB Output is correct
54 Correct 5 ms 2780 KB Output is correct
55 Correct 4 ms 2780 KB Output is correct
56 Correct 5 ms 2768 KB Output is correct