Submission #766332

#	Time	Username	Problem	Language	Result	Execution time	Memory
766332		NK_	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	220 ms	1572 KiB

ho_t2

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using str = string;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K; cin >> N >> K;
	str S; cin >> S;

	V<deque<int>> oc(3);

	auto verify = [&]() {
		// cout << "VERIFY: " << endl;
		int cur = -1;
		for(int t = 0; t < 3; t++) {
			int lo = 0, hi = sz(oc[t]);
			while(lo < hi) {
				int mid = (lo + hi) / 2;

				if (oc[t][mid] >= cur) hi = mid;
				else lo = mid + 1;
			}	

			int I = lo + K - 1; 
			if (I >= sz(oc[t])) return 0;
			cur = oc[t][I];
		}
		return 1;
	};

	auto check = [&](int w) {
		for(int t = 0; t < 3; t++) oc[t].clear();

		for(int i = 0; i < w; i++) {
			int t = (S[i] == 'J' ? 0 : (S[i] == 'O' ? 1 : 2));
			oc[t].push_back(i);
		}

		if (verify()) return 1;

		for(int i = w; i < N; i++) {
			int tb = (S[i-w] == 'J' ? 0 : (S[i-w] == 'O' ? 1 : 2));
			oc[tb].pop_front();

			int tf = (S[i] == 'J' ? 0 : (S[i] == 'O' ? 1 : 2));
			oc[tf].push_back(i);

			if (verify()) return 1;
		}
		return 0;
	};

	int lo = 3 * K, hi = N + 1;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
			
		// cout << lo << " <-> " << mid << " <-> " << hi << endl;

		if (check(mid)) hi = mid;
		else lo = mid + 1;
	}
	if (lo == N + 1) cout << -1 << nl;
	else cout << lo - 3 * K << nl;

    return 0;
}

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