Submission #1027120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027120		racsosabe	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	13 ms	3560 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

const int N = 200000 + 5;
const string JOI = "JOI";

int id(char c) {
	for(int i = 0; i < JOI.size(); i++) {
		if(JOI[i] == c) return i;
	}
	return -1;
}

int n;
int k;
string s;
int prefix[3][N];

int get_first_k(int id, int l) {
	int lo = l, hi = n + 1;
	while(lo < hi) {
		int mi = lo + (hi - lo) / 2;
		if(prefix[id][mi] - prefix[id][l - 1] < k) lo = mi + 1;
		else hi = mi;
	}
	return lo;
}

int solve(int at) {
	int l = at;
	for(int i = 0; i < 3; i++) {
		int to = get_first_k(i, at);
		if(to > n) return -1;
		at = to;
	}
	return at - l + 1 - 3 * k;
}

int main() {
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> k >> s;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) prefix[j][i] = prefix[j][i - 1];
		prefix[id(s[i - 1])][i] += 1;
	}
	int res = -1;
	for(int i = 1; i <= n; i++) {
		if(s[i - 1] != 'J') continue;
		int cur = solve(i);
		if(cur == -1) continue;
		if(res == -1 or res > cur) res = cur;
	}
	cout << res << endl;
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int id(char)':
ho_t2.cpp:8:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for(int i = 0; i < JOI.size(); i++) {
      |                 ~~^~~~~~~~~~~~

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