Submission #869215

#	Time	Username	Problem	Language	Result	Execution time	Memory
869215		goodspeed0208	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	55 ms	14312 KiB

ho_t2

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

signed main() {
	int n, k;
	cin >> n>> k;
	string s;
	cin >> s;
	vector<int>v(n);
	for (int i = 0 ; i < n ; i++) {
		if (s[i] == 'J') v[i] = 0;
		else if (s[i] == 'O') v[i] = 1;
		else v[i] = 2;
	}
	vector<vector<int> >num(n, vector<int>(3, 0));
	vector<vector<int> >pos(3);
	num[0][v[0]]++;
	pos[v[0]].push_back(0);
	for (int i = 1 ; i < n ; i++) {
		num[i] = num[i-1];
		num[i][v[i]] = num[i-1][v[i]]+1;
		pos[v[i]].push_back(i);
	} 
	int mn = -1;
	for (int i = 0 ; i < n ; i++) {
		int l = i+k*3-2, r = n;
		while (l+1 < r) {
			int j = (l + r) / 2;
			//cout << l << " " << r << " " << j << endl;
			int numj, numi;
			if (i == 0) numj = 0;
			else numj = num[i-1][0];
			numi = num[j][2];
			if (numj + k > pos[0].size() || numi < k) {
				l = j;
				continue;
			}
			int posj = pos[0][(numj + k) - 1];
			int posi = pos[2][(numi - k + 1) - 1];
			if (num[posi][1] - num[posj][1] >= k) {
				//cout << i << " " << j << "\n";
				
				r = j;
			} else {
				l = j;
			}
		}
		if (r == n) break;
		//cout << i << " " << r << "\n";
		if (mn == -1) mn = r - i + 1;
		else mn = min(mn, r-i+1);
		//for (int j = i+k*3-1 ; j < n ; j++) {
			
		//}
	}
	if (mn == -1) cout << "-1\n";
	else cout << mn - k * 3 << "\n";
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    if (numj + k > pos[0].size() || numi < k) {
      |        ~~~~~~~~~^~~~~~~~~~~~~~~

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