oj.uz

Submission #997153

# Submission time Handle Problem Language Result Execution time Memory
997153 2024-06-11T18:16:05 Z giorgi_pkhaladze JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 10 ms 3612 KB 
#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((int)j.size()<m || (int)o.size()<m || (int)i.size()<m)
	{
		cout<<-1; 
		return 0;
	}
	//cout<<"GIO"; return 0;
	int ans=10000000;
	for(k=0; k<=(int)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==10000000)cout<<-1;
	else cout<<ans;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 468 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 468 KB Output is correct
36 Correct 8 ms 3120 KB Output is correct
37 Correct 9 ms 3168 KB Output is correct
38 Correct 9 ms 3192 KB Output is correct
39 Correct 10 ms 3356 KB Output is correct
40 Correct 7 ms 3612 KB Output is correct
41 Correct 9 ms 3612 KB Output is correct
42 Correct 9 ms 3168 KB Output is correct
43 Correct 5 ms 2388 KB Output is correct
44 Correct 5 ms 2848 KB Output is correct
45 Correct 8 ms 3612 KB Output is correct
46 Correct 8 ms 3608 KB Output is correct
47 Correct 7 ms 3612 KB Output is correct
48 Correct 7 ms 3228 KB Output is correct
49 Correct 5 ms 2660 KB Output is correct
50 Correct 8 ms 3612 KB Output is correct
51 Correct 7 ms 3608 KB Output is correct
52 Correct 5 ms 3240 KB Output is correct
53 Correct 6 ms 3212 KB Output is correct
54 Correct 4 ms 3112 KB Output is correct
55 Correct 4 ms 3588 KB Output is correct
56 Correct 3 ms 3112 KB Output is correct