제출 #532339

#제출 시각아이디문제언어결과실행 시간메모리
532339Nanashi_PandaJJOOII 2 (JOI20_ho_t2)C++14
13 / 100
2070 ms2936 KiB
#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;
vector <ll> locO;
vector <ll> locI;
int main() {
	scanf("%lld%lld", &n, &k);
	scanf("%s", str);
	s = 0;
	//枚舉J,greedyO跟I (upper_bound優化 
	for(ll i = 0; i < n; i++){
		if(str[i]=='J')locJ.push_back(i);
		if(str[i]=='O')locO.push_back(i);
		if(str[i]=='I')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;
//		printf("J%lld %lld\n", locJ[i+k-1], locJ[i]);
		s = upper_bound(locO.begin(), locO.end(), locJ[i+k-1])-locO.begin();
		if(s<0) ok = 0;
		for (ll j = 1; j < k; j++){
			s = upper_bound(locO.begin(), locO.end(), locO[s])-locO.begin();
			if(s<0||!ok){
				ok = 0;
				break;
			}
		}
		if(locO[s]<locJ[i+k-1]) ok = 0;
		if(ok){
			num+=locO[s]-locJ[i+k-1]-k;
//			printf("O%lld %lld\n", locO[s], locJ[i+k-1]);
			t = upper_bound(locI.begin(), locI.end(), locO[s])-locI.begin();
			if(t<0) ok = 0;
			for (ll j = 1; j<k; j++){
				t = upper_bound(locI.begin(), locI.end(), locI[t])-locI.begin();
				if(t<0||!ok) {
					ok = 0;
					break;
				}
			}
			if(locI[t]<locO[s])ok = 0;
			if(ok) {
				num+=locI[t]-locO[s]-k;
				ans = min(num, ans);
//				printf("I%lld %lld\n", locI[t], locO[s]);
			}
				
		}
//		printf("%d ", ok);
//		if(ok)
//			printf("%lld\n", num);
//		else
//			printf("-1\n");
	}
	if(ans<200000)
		printf("%lld", ans);
	else
		printf("-1");
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:26:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   26 |  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);
      |  ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...