Submission #241606

#	Time	Username	Problem	Language	Result	Execution time	Memory
241606		verngutz	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	13 ms	4476 KiB

ho_t2

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans = lim<int>::max();
    vector<int> J, O, I, jumpJ(n + 1, -1), jumpO(n + 1, -1), jumpI(n + 1, -1);
    for(int i = 0; i < n; i++) {
        if(s[i] == 'J') {
            J.push_back(i);
        } else if(s[i] == 'O') {
            O.push_back(i);
        } else {
            I.push_back(i);
        }
    }
    for(int i = (k - 1 < J.size() ? J[k - 1] + 1 : n), j = 0; i < n; i++) {
        jumpJ[i] = J[j];
        if(s[i] == 'J') {
            j++;
        }
    }
    for(int i = (O.size() - k >= 0 ? O[O.size() - k] - 1 : -1), j = O.size() - 1; i >= 0; i--) {
        jumpO[i] = O[j];
        if(s[i] == 'O') {
            j--;
        }
    }
    for(int i = (I.size() - k >= 0 ? I[I.size() - k] - 1 : -1), j = I.size() - 1; i >= 0; i--) {
        jumpI[i] = I[j];
        if(s[i] == 'I') {
            j--;
        }
    }
    for(int i = 1; i < n; i++) {
        if(s[i] == 'O') {
            int j = jumpO[i - 1];
            if(jumpJ[i] != -1 and jumpO[i - 1] != -1 and jumpI[j] != -1) {
                ans = min(ans, (i - jumpJ[i]) + (j - i + 1) + (jumpI[j] - j) - 3 * k);
            }
        }
    }
    cout << (ans < lim<int>::max() ? ans : -1) << endl;
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = (k - 1 < J.size() ? J[k - 1] + 1 : n), j = 0; i < n; i++) {
                  ~~~~~~^~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87