Submission #201586

#TimeUsernameProblemLanguageResultExecution timeMemory
201586MvCJJOOII 2 (JOI20_ho_t2)C++11
100 / 100
19 ms1652 KiB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int n,k,i,j,t,sz[3],rs;
char c;
vector<int>vc[3];
int get(char ch)
{
	if(ch=='J')return 0;
	else if(ch=='O')return 1;
	else return 2;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>c;
		vc[get(c)].pb(i);
	}
	rs=inf;
	for(i=0;i<3;i++)sz[i]=(int)vc[i].size();
	for(i=0;i<sz[0];i++)
	{
		if(i+k<=sz[0])
		{
			j=lower_bound(vc[1].begin(),vc[1].end(),vc[0][i+k-1])-vc[1].begin();
			if(j+k<=sz[1])
			{
				t=lower_bound(vc[2].begin(),vc[2].end(),vc[1][j+k-1])-vc[2].begin();
				if(t+k<=sz[2])rs=min(rs,vc[2][t+k-1]-vc[0][i]+1);
				else break;
			}
			else break;
		}
		else break;
	}
	if(rs==inf)cout<<-1<<endl;
	else cout<<rs-3*k<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...