Submission #1057162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057162		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	13 ms	3204 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 2e5 + 5;
 
int N, K;
char a[MAXN];
int cnt[3][MAXN];
 
int get(int l, int r, int c) {
    return cnt[c][r] - cnt[c][l - 1];
}
 
int find_left(int p) {
    int low = 1, high = p;
    int ans = -1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(get(mid, p, 0) == K) {
            ans = mid;
            low = mid + 1;
        } else if(get(mid, p, 0) > K)
            low = mid + 1;
        else if(get(mid, p, 0) < K)
            high = mid - 1;
    }
    return ans;
}
 
int find_right(int p) {
    int low = p, high = N;
    int ans = -1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(get(p, mid, 2) == K) {
            ans = mid;
            high = mid - 1;
        } else if(get(p, mid, 2) > K)
            high = mid - 1;
        else if(get(p, mid, 2) < K)
            low = mid + 1;
    }
    return ans;
}
 
signed main() {
#define TASK "code"
 
    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < 3; j++)
            cnt[j][i] = cnt[j][i - 1];
        if(a[i] == 'J')
            cnt[0][i]++;
        else if(a[i] == 'O')
            cnt[1][i]++;
        else if(a[i] == 'I')
            cnt[2][i]++;
    }
    int ans = N + 1;
    for(int i = 1; i <= N; i++) {
        if(a[i] != 'O') continue;
        bool ok = true;
        int res = 0;
        int low = i, high = N;
        int p = -1;
        while(low <= high) {
            int mid = (low + high) / 2;
            if(get(i, mid, 1) == K) {
                p = mid;
                high = mid - 1;
            } else if(get(i, mid, 1) > K)
                high = mid - 1;
            else if(get(i, mid, 1) < K)
                low = mid + 1;
        }
 
        if(p == -1) break;
        res += (p - i + 1) - K;
 
        {
            int x = find_left(i - 1);
            if(x == -1) ok = false;
            res += ((i - 1) - x + 1) - K;
        }
 
        {
            int x = find_right(p + 1);
            if(x == -1) ok = false;
            res += (x - (p + 1) + 1) - K;
        }
        if(ok) ans = min(ans, res);
    }
    cout << (ans == N + 1 ? -1 : ans);
    return (0 ^ 0);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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