Submission #556535

#	Time	Username	Problem	Language	Result	Execution time	Memory
556535		alextodoran	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	7 ms	2372 KiB

ho_t2

/**
 ____ ____ ____ ____ ____
||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 (stderr)

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 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87