Submission #650057

#	Time	Username	Problem	Language	Result	Execution time	Memory
650057		TheEvilBird	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	13 ms	2012 KiB

ho_t2

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

#ifdef __APPLE__
#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> pos_j, pos_i;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'J') {
            pos_j.emplace_back(i);
        }
    }
    for (int i = n - 1; i > -1; --i) {
        if (s[i] == 'I') {
            pos_i.emplace_back(i);
        }
    }
    if (sz(pos_j) < k || sz(pos_i) < k) {
        cout << -1 << en;
        return;
    }
    vector<int> pos_o;
    for (int i = pos_j[k - 1] + 1; i < pos_i[k - 1]; ++i) {
        if (s[i] == 'O') {
            pos_o.emplace_back(i);
        }
    }
    if (sz(pos_o) < k) {
        cout << -1 << en;
        return;
    }

    int ans = n;
    reverse(all(pos_i));
//    int ptr_j = k - 1, ptr_o = 0, ptr_i = 0;
//    while (pos_i[ptr_i] < pos_o[ptr_o + k - 1]) {
//        ++ptr_i;
//    }
//
//    pos_j.emplace_back(-1);
//    pos_i.emplace_back(n + 1);
//
//    while (ptr_j < sz(pos_j) && ptr_o + k - 1 < sz(pos_o) && ptr_i + k - 1 < sz(pos_i)) {
//        int l = pos_j[ptr_j - k + 1], r = pos_i[ptr_i + k - 1];
//        ans = min(ans, r - l + 1 - 3 * k);
//        ++ptr_o;
//        if (!(ptr_o + k - 1 < sz(pos_o))) {
//            break;
//        }
//        while (ptr_i < sz(pos_i) && pos_i[ptr_i] < pos_o[ptr_o + k - 1]) {
//            ++ptr_i;
//        }
//        while (ptr_j + 1 < sz(pos_j) && pos_o[ptr_o] < pos_j[ptr_j + 1]) {
//            ++ptr_j;
//        }
//    }
    for (int i = 0; i + k - 1 < sz(pos_o); ++i) {
        int o1 = pos_o[i], o2 = pos_o[i + k - 1];
        int id_j = (int)(lower_bound(all(pos_j), o1) - pos_j.begin());
        --id_j;
//        while (id_j > -1 && o1 < pos_j[id_j]) {
//            --id_j;
//        }
        if (id_j - k + 1 < 0) {
            continue;
        }
        int id_i = (int)(lower_bound(all(pos_i), o2) - pos_i.begin());
        if (id_i + k - 1 >= sz(pos_i)) {
            continue;
        }
        int l = pos_j[id_j - k + 1], r = pos_i[id_i + k - 1];
        ans = min(ans, r - l + 1 - 3 * k);
    }
    cout << ans << en;
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
    return 0;
}

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