Submission #423372

#	Time	Username	Problem	Language	Result	Execution time	Memory
423372		tengiz05	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	204 KiB

ho_t2

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;
    std::vector<std::vector<int>> pr(3, std::vector<int>(n + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            pr[j][i + 1] = pr[j][i] + (std::string("JOI").find(s[i]) == j);
        }
    }
    int ans = n + 1;
    for (int i = k; i <= n - 2 * k; i++) {
        if (pr[0][i] < k || pr[1][n] - pr[1][i] < k) {
            continue;
        }
        auto check = [&](int j) {
            if (pr[1][j] - pr[1][i] < k) {
                return -1;
            }
            int l = j + 1, r = n + 1;
            while (l + 1 < r) {
                int mid = (l + r) / 2;
                if (pr[2][mid] - pr[2][j] >= k) {
                    r = mid;
                } else {
                    l = mid;
                }
            }
            if (r <= n) {
                return r;
            }
            return -2;
        };
        int l = i + 1, r = n + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (~check(mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        if (r <= n) {
            r = check(r);
            int L = 0, R = i + 1;
            while (L + 1 < R) {
                int mid = (L + R) / 2;
                if (pr[0][i] - pr[0][mid - 1] >= k) {
                    L = mid;
                } else {
                    R = mid;
                }
            }
            if (r > 0)
                ans = std::min(ans, r - L + 1 - 3 * k);
        }
    }
    if (ans > n) {
        std::cout << -1 << "\n";
    } else {
        std::cout << ans << "\n";
    }
    return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:12:70: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |             pr[j][i + 1] = pr[j][i] + (std::string("JOI").find(s[i]) == j);
      |                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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