Submission #205314

#	Time	Username	Problem	Language	Result	Execution time	Memory
205314		TadijaSebez	JJOOII 2 (JOI20_ho_t2)	C++11	100 / 100	31 ms	2936 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
const int N=200050;
const int inf=1e9+7;
int J[N],O[N],I[N];
char str[N];
int main(){
	int n,k;
	scanf("%i %i",&n,&k);
	scanf("%s",str+1);
	for(int i=1;i<=n;i++){
		J[i]=J[i-1]+(str[i]=='J');
		O[i]=O[i-1]+(str[i]=='O');
		I[i]=I[i-1]+(str[i]=='I');
	}
	int ans=inf;
	for(int i=1;i<=n;i++){
		int top=n,bot=i,mid,pos=n+1;
		while(top>=bot){
			mid=top+bot>>1;
			if(J[mid]-J[i-1]>=k)pos=mid,top=mid-1;
			else bot=mid+1;
		}
		if(pos==n+1)continue;
		int tmp=pos;
		top=n,bot=pos+1,pos=n+1;
		while(top>=bot){
			mid=top+bot>>1;
			if(O[mid]-O[tmp]>=k)pos=mid,top=mid-1;
			else bot=mid+1;
		}
		if(pos==n+1)continue;
		tmp=pos;
		top=n,bot=pos+1,pos=n+1;
		while(top>=bot){
			mid=top+bot>>1;
			if(I[mid]-I[tmp]>=k)pos=mid,top=mid-1;
			else bot=mid+1;
		}
		if(pos==n+1)continue;
		ans=min(ans,pos-i+1-3*k);
	}
	if(ans==inf)printf("-1\n");
	else printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:20:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
ho_t2.cpp:28:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
ho_t2.cpp:36:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid=top+bot>>1;
        ~~~^~~~
ho_t2.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
ho_t2.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str+1);
  ~~~~~^~~~~~~~~~~~

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