oj.uz

Submission #766325

# Submission time Handle Problem Language Result Execution time Memory
766325 2023-06-25T13:44:16 Z NK_ JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 1 ms 212 KB 
// 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++) {
			// cout << t << endl;
			// for(auto x : oc[t]) cout << x << " ";
			// cout << endl << endl;

			// cout << "CUR: " << cur << endl;
			int lo = 0, hi = sz(oc[t]);
			while(lo < hi) {
				int mid = (lo + hi) / 2;
				// cout << lo << " " << mid << " " << hi << endl;
				// cout << oc[t][mid] << endl;

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

			int I = lo + K - 1; 
			// cout << "I: "  << I << " " << sz(oc[t]) << endl; 
			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;
	}

	cout << N - lo << nl;

    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -