Submission #532463

#	Time	Username	Problem	Language	Result	Execution time	Memory
532463		Nanashi_Panda	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	11 ms	3240 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);
	}
	ll num = 0;
	bool ok = 1;
	for(ll i = 0; i < locJ.size()-k+1; i++){
		num=locJ[i+k-1]-locJ[i]+1-k;
		ok = 1;
		it = upper_bound(locO.begin(), locO.end(), locJ[i+k-1]);
		if(it == locO.end()) ok = 0;
		if(ok){
			s = it-locO.begin();
			if(s+k-1>=locO.size()) ok = 0;
			else num+=locO[s+k-1]-locJ[i+k-1]-k;
			if(ok){
				it = upper_bound(locI.begin(), locI.end(), locO[s+k-1]);
				if(it==locI.end()) ok = 0;
				else{
					t = it-locI.begin();
					if(t+k-1>=locI.size()) ok = 0;
					else num+=locI[t+k-1]-locO[s+k-1]-k;
					if(ok) {
						ans = min(num, ans);
					}
				}
					
			}
		}
		if(!ok) break;
	}
	if(ans<200000)
		printf("%lld", ans);
	else
		printf("-1");
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:27:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   27 |  for(ll i = 0; i < locJ.size()-k+1; i++){
      |                ~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:34:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    if(s+k-1>=locO.size()) ok = 0;
      |       ~~~~~^~~~~~~~~~~~~
ho_t2.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |      if(t+k-1>=locI.size()) ok = 0;
      |         ~~~~~^~~~~~~~~~~~~
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: 87 / 87