oj.uz

Submission #556535

# Submission time Handle Problem Language Result Execution time Memory
556535 2022-05-03T10:10:04 Z alextodoran JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 7 ms 2372 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N, K;
string S;

int first[CHAR_MAX];
int nxt[N_MAX];

deque <int> dq[CHAR_MAX];

bool fix (char c, int pref) {
    while (dq[c].empty() == false && dq[c].front() <= pref) {
        dq[c].push_back(nxt[dq[c].back()]);
        dq[c].pop_front();
    }
    return (dq[c].back() != N);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;
    cin >> S;

    first['J'] = first['O'] = first['I'] = N;
    nxt[N] = N;
    for (int i = N - 1; i >= 0; i--) {
        nxt[i] = first[S[i]];
        first[S[i]] = i;
    }

    for (int i = 0; i < N; i++) {
        if ((int) dq['J'].size() < K) {
            if (S[i] == 'J') {
                dq['J'].push_back(i);
            }
        } else if ((int) dq['O'].size() < K) {
            if (S[i] == 'O') {
                dq['O'].push_back(i);
            }
        } else if ((int) dq['I'].size() < K) {
            if (S[i] == 'I') {
                dq['I'].push_back(i);
            }
        }
    }

    if ((int) dq['I'].size() < K) {
        cout << -1 << "\n";
        return 0;
    }

    int maxDel = 0;
    for (int pref = 0; pref < N; pref++) {
        maxDel = max(maxDel, pref + (N - 1) - dq['I'].back());
        if (S[pref] == 'J') {
            if (fix('J', pref) == false) {
                break;
            }
            if (fix('O', dq['J'].back()) == false) {
                break;
            }
            if (fix('I', dq['O'].back()) == false) {
                break;
            }
        }
    }
    cout << N - K * 3 - maxDel << "\n";

    return 0;
}

Compilation message

ho_t2.cpp: In function 'bool fix(char, int)':
ho_t2.cpp:26:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |     while (dq[c].empty() == false && dq[c].front() <= pref) {
      |               ^
ho_t2.cpp:26:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |     while (dq[c].empty() == false && dq[c].front() <= pref) {
      |                                         ^
ho_t2.cpp:27:12: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |         dq[c].push_back(nxt[dq[c].back()]);
      |            ^
ho_t2.cpp:27:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |         dq[c].push_back(nxt[dq[c].back()]);
      |                                ^
ho_t2.cpp:28:12: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |         dq[c].pop_front();
      |            ^
ho_t2.cpp:30:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |     return (dq[c].back() != N);
      |                ^
ho_t2.cpp: In function 'int main()':
ho_t2.cpp:44:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |         nxt[i] = first[S[i]];
      |                            ^
ho_t2.cpp:45:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |         first[S[i]] = i;
      |                   ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 412 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 408 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 408 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 412 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 408 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 408 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 412 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 412 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 412 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 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 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 416 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 412 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 408 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 408 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 412 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 412 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 412 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 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 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 416 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 7 ms 1632 KB Output is correct
37 Correct 7 ms 1608 KB Output is correct
38 Correct 6 ms 1704 KB Output is correct
39 Correct 7 ms 1632 KB Output is correct
40 Correct 5 ms 1760 KB Output is correct
41 Correct 6 ms 1696 KB Output is correct
42 Correct 7 ms 1632 KB Output is correct
43 Correct 3 ms 1268 KB Output is correct
44 Correct 3 ms 1504 KB Output is correct
45 Correct 3 ms 1760 KB Output is correct
46 Correct 4 ms 1760 KB Output is correct
47 Correct 4 ms 1848 KB Output is correct
48 Correct 4 ms 1760 KB Output is correct
49 Correct 3 ms 1376 KB Output is correct
50 Correct 4 ms 1760 KB Output is correct
51 Correct 4 ms 1760 KB Output is correct
52 Correct 4 ms 1744 KB Output is correct
53 Correct 4 ms 1836 KB Output is correct
54 Correct 4 ms 1632 KB Output is correct
55 Correct 4 ms 2144 KB Output is correct
56 Correct 3 ms 2372 KB Output is correct