제출 #753809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
753809		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	434 ms	5808 KiB

ho_t2

// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define int long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;

const ll INF = LONG_MAX;
const int N =  2e6;
const int M = 1e9 + 7;
const ll HZ = 998244353;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;

int n,k,ps[3][N];
string s;

int find_pos(int L,int R,int val) {
    int l=L,r=R;
    while (l+1<r) {
        int mid=(l+r)/2;
        if (ps[val][mid]-ps[val][L]<k)
            l=mid;
        else
            r=mid;
    }
    return r;
}

bool ch(int l,int r) {
    int z1 = find_pos(l, r, 0), z2 = find_pos(z1, r, 1), z3 = find_pos(z2, r, 2);
    return ps[0][z1] - ps[0][l] >= k and ps[1][z2] - ps[1][z1] >= k and ps[2][z3] - ps[2][z2] >= k;
}

void solve() {
    s += ' ';
    string t;
    cin >> n >> k >> t;
    s += t;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++)
            ps[j][i] = ps[j][i - 1];
        if (s[i] == 'J')
            ps[0][i]++;
        if (s[i] == 'O')
            ps[1][i]++;
        if (s[i] == 'I')
            ps[2][i]++;
    }
    if (!ch(0, n)) {
        cout << -1;
        return;
    }
    int mn = INT_MAX;
    for (int i = 0; i <= n; i++) {
        int l = i, r = n + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (ch(i, mid))
                r = mid;
            else
                l = mid;
        }
        if (r == n + 1)
            break;
        mn = min(mn, r - i);
    }
    cout << mn - k * 3;
}

signed main() {
    // freopen("262144.in", "r", stdin);
    // freopen("262144.out", "w", stdout);
    kanagattandirilmagandiktarinizdan
    int test = 1;
    // cin >> test;
    for (int i=1;i<=test;i++) {
        // cout << "Case " << i << ':' << '\n';
        solve();
        // cout << '\n';
    }
    return 0;
}

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