Submission #736443

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
736443	2023-05-05T16:23:39 Z	LCJLY	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	6 ms	2400 KB

ho_t2

#include <bits/stdc++.h>
using namespace std;

#define int long long 
typedef pair<int,int>pii;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	
	deque<int>v; //stores index of j
	deque<int>v2; //store index of o
	deque<int>v3; //store index of i
	
	for(int x=0;x<n;x++){
		if(s[x]=='J'){
			v.push_back(x);
		}
		else if(s[x]=='O'){
			v2.push_back(x);
		}
		else{
			v3.push_back(x);
		}
	}
	
	int best=INT_MAX;
	
	for(int x=k-1;x<v.size();x++){
		int l2=v[x-k+1];
		int l=v[x];
		//cout << l << " left\n";
		while(!v2.empty()&&v2.front()<l){
			v2.pop_front();
		}
		
		if(v2.size()<k) continue;
		int mid=v2[k-1];
		//cout << mid << " mid\n";
		while(!v3.empty()&&v3.front()<mid){
			v3.pop_front();
		}
		if(v3.size()<k) continue;
		int r=v3[k-1];
		//cout << r << " right\n";
		
		int hold=r-l2+1-3*k;
		best=min(best,hold);
	}
	
	if(best==INT_MAX) cout << -1;
	else cout << best;
	
	
	
}

Compilation message

ho_t2.cpp: In function 'int32_t main()':
ho_t2.cpp:34:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int x=k-1;x<v.size();x++){
      |                ~^~~~~~~~~
ho_t2.cpp:42:15: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   42 |   if(v2.size()<k) continue;
      |      ~~~~~~~~~^~
ho_t2.cpp:48:15: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   48 |   if(v3.size()<k) continue;
      |      ~~~~~~~~~^~

Subtask #1
1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	316 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	316 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	316 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	324 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	324 KB	Output is correct
29	Correct	1 ms	316 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	312 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct

Subtask #3
87.0 / 87.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	316 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	316 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 ms	300 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	316 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	324 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	324 KB	Output is correct
29	Correct	1 ms	316 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	312 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	6 ms	2128 KB	Output is correct
37	Correct	6 ms	2284 KB	Output is correct
38	Correct	6 ms	2284 KB	Output is correct
39	Correct	5 ms	2272 KB	Output is correct
40	Correct	5 ms	2296 KB	Output is correct
41	Correct	6 ms	2400 KB	Output is correct
42	Correct	6 ms	2272 KB	Output is correct
43	Correct	3 ms	1492 KB	Output is correct
44	Correct	4 ms	1888 KB	Output is correct
45	Correct	5 ms	2272 KB	Output is correct
46	Correct	5 ms	2372 KB	Output is correct
47	Correct	5 ms	2260 KB	Output is correct
48	Correct	5 ms	2392 KB	Output is correct
49	Correct	4 ms	1632 KB	Output is correct
50	Correct	5 ms	2272 KB	Output is correct
51	Correct	5 ms	2372 KB	Output is correct
52	Correct	4 ms	2240 KB	Output is correct
53	Correct	5 ms	2272 KB	Output is correct
54	Correct	4 ms	2388 KB	Output is correct
55	Correct	3 ms	2284 KB	Output is correct
56	Correct	3 ms	2400 KB	Output is correct

Submission #736443

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 12.0 / 12.0

Subtask #3 87.0 / 87.0

Subtask #1
1.0 / 1.0

Subtask #2
12.0 / 12.0

Subtask #3
87.0 / 87.0