Submission #205561

#	Time	Username	Problem	Language	Result	Execution time	Memory
205561		nafis_shifat	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	32 ms	3128 KiB

ho_t2

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;

int bs(int lo,int hi,int *ar,int k)
{
	int in;
	if(lo>0)in=ar[lo-1];
	else in=0;
	int rs=-1;
	
	//cout<<ar[1]<<endl;
	while(lo<=hi)
	{
		int mid=lo+hi>>1;
		if(ar[mid]-in>=k)
		{
			rs=mid;
			hi=mid-1;
		}
		else lo=mid+1;
	}

	return rs;
}

int main()
{
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;

	int J[n]={};
	int O[n]={};
	int I[n]={};
	if(s[0]=='J')J[0]++;
	else if(s[0]=='O')O[0]++;
	else I[0]++;

	int ans=1e9+10;



	for(int i=1;i<n;i++)
	{
		J[i]=J[i-1];
		O[i]=O[i-1];
		I[i]=I[i-1];
		if(s[i]=='J')J[i]++;
	    else if(s[i]=='O')O[i]++;
	    else I[i]++;
	}

	for(int i=0;i<n;i++)
	{
		if(s[i]!='J')continue;
		int n1=bs(i,n-1,J,k);
        
		if(n1==-1)continue;
		int n2=bs(n1+1,n-1,O,k);
		if(n2==-1)continue;
		int n3=bs(n2+1,n-1,I,k);
		if(n3==-1)continue;
		
		

		int d=n3-i+1;
		d-=3*k;

		ans=min(d,ans);


	}
    if(ans==1e9+10)cout<<-1<<endl;
	else cout<<ans<<endl;



	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int bs(int, int, int*, int)':
ho_t2.cpp:16:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=lo+hi>>1;
           ~~^~~

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