Submission #736443

#	Time	Username	Problem	Language	Result	Execution time	Memory
736443		LCJLY	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	6 ms	2400 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

#define int long long 
typedef pair<int,int>pii;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	
	deque<int>v; //stores index of j
	deque<int>v2; //store index of o
	deque<int>v3; //store index of i
	
	for(int x=0;x<n;x++){
		if(s[x]=='J'){
			v.push_back(x);
		}
		else if(s[x]=='O'){
			v2.push_back(x);
		}
		else{
			v3.push_back(x);
		}
	}
	
	int best=INT_MAX;
	
	for(int x=k-1;x<v.size();x++){
		int l2=v[x-k+1];
		int l=v[x];
		//cout << l << " left\n";
		while(!v2.empty()&&v2.front()<l){
			v2.pop_front();
		}
		
		if(v2.size()<k) continue;
		int mid=v2[k-1];
		//cout << mid << " mid\n";
		while(!v3.empty()&&v3.front()<mid){
			v3.pop_front();
		}
		if(v3.size()<k) continue;
		int r=v3[k-1];
		//cout << r << " right\n";
		
		int hold=r-l2+1-3*k;
		best=min(best,hold);
	}
	
	if(best==INT_MAX) cout << -1;
	else cout << best;
	
	
	
}

Compilation message (stderr)

ho_t2.cpp: In function 'int32_t main()':
ho_t2.cpp:34:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int x=k-1;x<v.size();x++){
      |                ~^~~~~~~~~
ho_t2.cpp:42:15: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   42 |   if(v2.size()<k) continue;
      |      ~~~~~~~~~^~
ho_t2.cpp:48:15: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   48 |   if(v3.size()<k) continue;
      |      ~~~~~~~~~^~

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