Submission #352622

#	Time	Username	Problem	Language	Result	Execution time	Memory
352622		mariowong	JJOOII 2 (JOI20_ho_t2)	C++14	0 / 100	1 ms	364 KiB

ho_t2

#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define pbb pair<bool,bool>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xmod (ll)(1e9+7) 
#define hmod 1286031825167LL
using namespace std;

int n,k,len,pt1,pt2,sum,ans;
string s;
vector <int> pos[5];
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> s; len=s.length();
	for (int i=0;i<len;i++){
		if (s[i] == 'J')
		pos[0].pb(i);
		if (s[i] == 'O')
		pos[1].pb(i);
		if (s[i] == 'I')
		pos[2].pb(i);
	}
	ans=1e9;
	if (k-1 > (int)pos[1].size()-1 && k-1 > (int)pos[2].size()-1 && k-1 > pos[0].size()-1){
		cout << "-1\n";
		return 0;
	}
	for (int i=1;i<=k-1;i++){
		sum+=pos[0][i]-pos[0][i-1]-1;
		sum+=pos[1][i]-pos[1][i-1]-1;
		sum+=pos[2][i]-pos[2][i-1]-1;
	}
	pt1=k-1; pt2=k-1;
	for (int i=k-1;i<pos[0].size();i++){
		while (pt1 < (int)pos[1].size() && pos[1][pt1-(k-1)] < pos[0][i]){
			sum-=(pos[1][pt1-(k-2)]-pos[1][pt1-(k-1)]-1);
			pt1++;
			if (pt1 == (int)pos[1].size())
			goto out;
			sum+=(pos[1][pt1]-pos[1][pt1-1]-1);
		} 
		while (pt2 < (int)pos[2].size() && pos[2][pt2-(k-1)] < pos[1][pt1]){
			sum-=(pos[2][pt2-(k-2)]-pos[2][pt2-(k-1)]-1);
			pt2++;
			if (pt2 == (int)pos[2].size())
			goto out;
			sum+=(pos[2][pt2]-pos[2][pt2-1]-1);
		}
		ans=min(ans,sum);
	}
	out:;
	if (ans == 1e9)
	cout << "-1\n";
	else
	cout << ans << "\n";
    return 0;	
}	

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:32:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  if (k-1 > (int)pos[1].size()-1 && k-1 > (int)pos[2].size()-1 && k-1 > pos[0].size()-1){
      |                                                                  ~~~~^~~~~~~~~~~~~~~~~
ho_t2.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i=k-1;i<pos[0].size();i++){
      |                 ~^~~~~~~~~~~~~~

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