Submission #716237

#	Time	Username	Problem	Language	Result	Execution time	Memory
716237		hpesoj	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	8 ms	4024 KiB

ho_t2

#include <bits/stdc++.h>
//#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
#define debug4(x, y, z, w) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << ' ' << #w << ": " << w << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int inf = 1000000000;
int n, k, JJ, OO, II;
string s;
vector <int> J, O, I;
int ans = inf, nearestj[300005], nearesto[300005], nearesti[300005];
int nearest(char x, int i){
	if(x == 'J'){
		if(i + k - 1 >= JJ) return inf;
		else return J[i+k-1];
	}
	else if(x == 'O'){
		if(i + k - 1 >= OO) return inf;
		else return O[i+k-1];
	}
	else{
		if(i + k - 1 >= II) return inf;
		else return I[i+k-1];
	}
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k >> s;
	for(int i = 0; i < n; i++){
		if(s[i] == 'J') J.pb(i);
		else if(s[i] == 'O') O.pb(i);
		else I.pb(i);
	}
	JJ = J.size(), OO = O.size(); II = I.size();
	int i = 0;
	for(int j = 0; j < JJ; j++){
		int x = nearest('J', j);
		for(; i <= J[j]; i++) nearestj[i] = x;
	}
	for(; i <= n; i++) nearestj[i] = inf;
	i = 0;
	for(int j = 0; j < OO; j++){
		int x = nearest('O', j);
		for(; i <= O[j]; i++) nearesto[i] = x;
	}
	for(; i <= n; i++) nearesto[i] = inf;
	i = 0;
	for(int j = 0; j < II; j++){
		int x = nearest('I', j);
		for(; i <= I[j]; i++) nearesti[i] = x;
	}
	for(; i <= n; i++) nearesti[i] = inf;
	//for(int i = 0; i < n; i++) cout << nearestj[i] << ' ' << nearesto[i] << ' ' << nearesti[i] << '\n';
	for(i = 0; i < JJ; i++){
		int r1 = nearestj[J[i]];
		int r2 = (r1 == inf ? inf : nearesto[r1+1]);
		int r3 = (r2 == inf ? inf : nearesti[r2+1]);
		//debug4(J[i], r1, r2, r3);
		if(r3 == inf) continue;
		ans = min(ans, r3-J[i]+1 - 3 * k);
	}
	cout << (ans == inf ? -1 : ans);
}

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