Submission #532346

#	Time	Username	Problem	Language	Result	Execution time	Memory
532346		Nanashi_Panda	JJOOII 2 (JOI20_ho_t2)	C++14	13 / 100	2047 ms	2700 KiB

ho_t2

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#define jizz ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define ll long long
using namespace std;
char str[200005];
ll s,t;
ll n, k;
ll ans = 200005;
ll loc, cnt;

vector <ll> locJ, locO, locI;
vector <ll>::iterator it;
int main() {
	scanf("%lld%lld", &n, &k);
	scanf("%s", str);
	s = 0;
	for(ll i = 0; i < n; i++){
		if(str[i]=='J')locJ.push_back(i);
		else if(str[i]=='O')locO.push_back(i);
		else locI.push_back(i);
	}
	for(ll i = 0; i < locJ.size()-k+1; i++){
		ll num = 0;
		bool ok = 1;
		num+=locJ[i+k-1]-locJ[i]+1-k;
		it = upper_bound(locO.begin(), locO.end(), locJ[i+k-1]);
		if(it == locO.end()) ok = 0;
		if(ok){
			s = it-locO.begin();
			for (ll j = 1; j < k; j++){
				it = upper_bound(locO.begin(), locO.end(), locO[s]);
				if(it==locO.end()||!ok){
					ok = 0;
					break;
				}
				s = it-locO.begin();
			}
			if(ok){
				num+=locO[s]-locJ[i+k-1]-k;
				it = upper_bound(locI.begin(), locI.end(), locO[s]);
				if(it==locI.end()) ok = 0;
				if(ok){
					t = it-locI.begin();
					for (ll j = 1; j<k; j++){
						it = upper_bound(locI.begin(), locI.end(), locI[t]);
						if(it==locI.end()||!ok) {
							ok = 0;
							break;
						}
						t = it-locI.begin();
					}
					if(ok) {
						num+=locI[t]-locO[s]-k;
						ans = min(num, ans);
					}
				}
					
			}
		}
	}
	if(ans<200000)
		printf("%lld", ans);
	else
		printf("-1");
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:25:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   25 |  for(ll i = 0; i < locJ.size()-k+1; i++){
      |                ~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  scanf("%lld%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%s", str);
      |  ~~~~~^~~~~~~~~~~

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