Submission #486249

#	Time	Username	Problem	Language	Result	Execution time	Memory
486249		PoPularPlusPlus	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	10 ms	2004 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

void solve(){
	int n , k;
	cin >> n >> k;
	string s;
	cin >> s;
	int cnt = 0;
	char c = 'J';
	vector<int> v[3];
	for(int i = 0; i < n; i++){
		if(s[i] == 'J')v[0].pb(i);
		else if(s[i] == 'O')v[1].pb(i);
		else v[2].pb(i);
		if(c == s[i] && c != 'a'){
			cnt++;
			if(cnt == k){
				cnt = 0;
				if(c == 'I'){
					c = 'a';
				}
				if(c == 'O')c = 'I';
				if(c == 'J')c = 'O';
			}
		}
	}
	if(c == 'a'){
		int ans = 1e9;
		for(int i = 0; i+(k-1) < (int)v[0].size(); i++){
			int last = v[0][i + (k-1)];
			int p = upper_bound(all(v[1]) , last) - v[1].begin();
			if(p + (k - 1) < (int)v[1].size()){
				p = upper_bound(all(v[2]) , v[1][p + (k-1)]) - v[2].begin();
				if(p + (k-1) < (int)v[2].size()){
					last = v[2][p + (k-1)];
					ans = min(ans , (last - v[0][i] + 1) - 3 * k);
				}
			}
		}
		cout << ans << '\n';
	}
	else {
		cout << -1 << '\n';
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

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