Submission #423376

#	Time	Username	Problem	Language	Result	Execution time	Memory
423376		milleniumEeee	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	887 ms	2992 KiB

ho_t2

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

const int INF = 1e9;
const int MAXN = (int)2e5 + 5;

vector <char> vec = {'J', 'O', 'I', '#'};
int cnt[1000];
int pref[MAXN][3];
int n, k;
string s;

int f(char c) {
	if (c == 'J') {
		return 0;
	}
	if (c == 'O') {
		return 1;
	}
	if (c == 'I') {
		return 2;
	}
}

int get_cnt(int l, int r, int type) {
	if (l > r) {
		return 0;
	}
	if (l == 0) {
		return pref[r][type];
	} else {
		return pref[r][type] - pref[l - 1][type];
	}
}

int find_pos(int l, int r, char ch, int k) {
	if (get_cnt(l, r, f(ch)) >= k) {
		int bl = l - 1, br = r;
		while (br - bl > 1) {
			int bmid = (bl + br) >> 1;
			if (get_cnt(l, bmid, f(ch)) >= k) {
				br = bmid;
			} else {
				bl = bmid;
			}
		}
		return br;
	} else {
		return -1;
	}
}

bool can(int l, int r, int k) {
	int opt_j = find_pos(l, r, 'J', k);
	if (opt_j == -1) {
		return false;
	}
	int opt_o = find_pos(opt_j + 1, r, 'O', k);
	if (opt_o == -1) {
		return false;
	}
	int opt_i = find_pos(opt_o + 1, r, 'I', k);
	if (opt_i == -1) {
		return false;
	}
	return true;
}

signed main() {
	fastInp;
	cin >> n >> k;
	cin >> s;
	for (int i = 0; i < n; i++) {
		if (i > 0) {
			for (int j = 0; j < 3; j++) {
				pref[i][j] = pref[i - 1][j];
			}	
		}
		pref[i][f(s[i])]++;
	}
	int ans = INF;
	for (int l = 0; l < n; l++) {
		if (can(l, n - 1, k)) {
			int bl = l, br = n - 1;
			while (br - bl > 1) {
				int bmid = (bl + br) >> 1;
				if (can(l, bmid, k)) {
					br = bmid;
				} else {
					bl = bmid;
				}
			}
			ans = min(ans, (br - l + 1) - k * 3);
		}
	}
	if (ans == INF) {
		ans = -1;
	}
	cout << ans << endl;
}
/*
10 2
OJIJOIOIIJ
*/

Compilation message (stderr)

ho_t2.cpp: In function 'int f(char)':
ho_t2.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^

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