QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#439493#8590. Problem Settergiorgi_pkhaladze0 0ms3632kbC++231.3kb2024-06-12 02:05:542024-06-12 02:05:56

Judging History

你现在查看的是最新测评结果

  • [2024-06-12 02:05:56]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3632kb
  • [2024-06-12 02:05:54]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
using namespace std;
vector <int> j,o,i;
int n,m,k,ans,a[200001],ph[200001],sh[200001];
string s;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	cin>>s;
	s=' '+s;
	if(m*3>n){
		cout<<-1;
		 return 0; 
	}
	for(k=1; k<=n; k++){
		ph[k]=ph[k-1];
		if(s[k]=='J')ph[k]++,j.pb(k);
		if(s[k]=='I')i.pb(k);
		if(s[k]=='O')o.pb(k);
	}
	for(k=n; k>0; k--){
	    sh[k]=sh[k+1];
		if(s[k]=='I')sh[k]++;
	}
	if(j.size()<m && o.size()<m && i.size()<n)
	{
		cout<<-1; 
		return 0;
	}
	//cout<<"GIO"; return 0;
	int ans=10000;
	for(k=0; k<=o.size()-m; k++){
	    //cout<<sh[o[k]]<<" "<<ph[o[k]]<<'\n';
		if(sh[o[k]]<m)break;
		if(ph[o[k]]>m)break;
		int pos1=lower_bound(j.begin(),j.end(),o[k])-1-j.begin();
		int pos2=lower_bound(i.begin(),i.end(),o[k+m-1])-i.begin();
		int sz=j[pos1]-j[pos1-m+1]-m; 
		if(pos1<m-1 || pos2>(int)i.size()-m)continue;
		//cout<<pos1+1<<" "<<pos2+1<<'\n';
		sz++; //cout<<sz<<'\n';
		sz+=i[pos2+m-1]-i[pos2]-m+1; //cout<<sz<<'\n';
		sz+=o[k+m-1]-o[k]-m+1; //ans=min(ans,sz); //cout<<ans<<'\n'; 
		ans=min(ans,i[pos2+m-1]-j[1+pos1-m]+1-3*m);
	}
	if(ans==10000)cout<<-1;
	else cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3632kb

input:

1000 1
570339 324084
75781 292531
427864 843267
928484 613828
883296 385343
733451 782070
756314 89477
786410 133722
455015 841750
146307 536680
992681 107898
657731 633895
764691 258779
142935 640379
445046 717170
227758 578083
526095 660806
859673 757597
898726 4088
719881 887973
850810 674331
752...

output:

-1

result:

wrong answer 1st lines differ - expected: '575102', found: '-1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 0ms
memory: 3624kb

input:

200000 200000
443848 257048
353855 430518
112240 460358
489050 850745
18217 643349
796031 335731
553602 81823
556808 39341
963397 797473
713023 273372
888193 500234
801660 980841
416233 163140
649254 659678
434013 461662
805451 259446
107168 839690
438518 100393
584335 435627
735040 11809
906814 672...

output:

-1

result:

wrong answer 1st lines differ - expected: '199985649927', found: '-1'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%