답안 #824656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
824656	2023-08-14T08:34:35 Z	kshitij_sodani	Rope (JOI17_rope)	C++17	80 / 100	2500 ms	81368 KB

rope

#include <bits/stdc++.h>
#define a first
#define b second
#define pb push_back
using namespace std;
#define endl '\n'
typedef long long llo;


int it[1000001];
int ans[1000001];
int co[1000001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		ans[i]=n;
	}
	for(int i=0;i<n;i++){
		cin>>it[i];
		it[i]--;
		co[it[i]]++;

		ans[it[i]]--;
	}
	map<pair<pair<int,int>,int>,int> ss;
	for(int i=0;i<n-1;i++){
		if(it[i]!=it[i+1]){
			ss[{{min(it[i],it[i+1]),max(it[i],it[i+1])},i%2}]++;
		}
	}
	
	for(int i=0;i<m;i++){
		for(int j=i+1;j<m;j++){
			int cur=co[i]+co[j];
			int mi=0;
			if(ss.find({{i,j},0})!=ss.end()){
				mi=ss[{{i,j},0}];
				if(ss.find({{i,j},1})!=ss.end()){
					mi=min(mi,ss[{{i,j},1}]);
				}
				else{
					mi=0;
				}
			}
			int co=cur-mi;
	
			
				ans[i]=min(ans[i],n-co);
				ans[j]=min(ans[j],n-co);
			
		}
	}

	for(int i=0;i<m;i++){
		cout<<ans[i]<<endl;

	}






	return 0;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 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	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 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	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	8 ms	724 KB	Output is correct
28	Correct	6 ms	724 KB	Output is correct
29	Correct	8 ms	636 KB	Output is correct
30	Correct	6 ms	724 KB	Output is correct
31	Correct	8 ms	724 KB	Output is correct
32	Correct	6 ms	724 KB	Output is correct
33	Correct	8 ms	724 KB	Output is correct
34	Correct	7 ms	724 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 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	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	8 ms	724 KB	Output is correct
28	Correct	6 ms	724 KB	Output is correct
29	Correct	8 ms	636 KB	Output is correct
30	Correct	6 ms	724 KB	Output is correct
31	Correct	8 ms	724 KB	Output is correct
32	Correct	6 ms	724 KB	Output is correct
33	Correct	8 ms	724 KB	Output is correct
34	Correct	7 ms	724 KB	Output is correct
35	Correct	47 ms	5880 KB	Output is correct
36	Correct	56 ms	6244 KB	Output is correct
37	Correct	47 ms	6180 KB	Output is correct
38	Correct	45 ms	6120 KB	Output is correct
39	Correct	45 ms	6236 KB	Output is correct
40	Correct	30 ms	3764 KB	Output is correct
41	Correct	31 ms	3696 KB	Output is correct
42	Correct	27 ms	3144 KB	Output is correct
43	Correct	26 ms	3068 KB	Output is correct
44	Correct	30 ms	3768 KB	Output is correct
45	Correct	30 ms	3800 KB	Output is correct
46	Correct	25 ms	3156 KB	Output is correct
47	Correct	25 ms	3028 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 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	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	8 ms	724 KB	Output is correct
28	Correct	6 ms	724 KB	Output is correct
29	Correct	8 ms	636 KB	Output is correct
30	Correct	6 ms	724 KB	Output is correct
31	Correct	8 ms	724 KB	Output is correct
32	Correct	6 ms	724 KB	Output is correct
33	Correct	8 ms	724 KB	Output is correct
34	Correct	7 ms	724 KB	Output is correct
35	Correct	47 ms	5880 KB	Output is correct
36	Correct	56 ms	6244 KB	Output is correct
37	Correct	47 ms	6180 KB	Output is correct
38	Correct	45 ms	6120 KB	Output is correct
39	Correct	45 ms	6236 KB	Output is correct
40	Correct	30 ms	3764 KB	Output is correct
41	Correct	31 ms	3696 KB	Output is correct
42	Correct	27 ms	3144 KB	Output is correct
43	Correct	26 ms	3068 KB	Output is correct
44	Correct	30 ms	3768 KB	Output is correct
45	Correct	30 ms	3800 KB	Output is correct
46	Correct	25 ms	3156 KB	Output is correct
47	Correct	25 ms	3028 KB	Output is correct
48	Correct	1200 ms	68028 KB	Output is correct
49	Correct	1208 ms	68032 KB	Output is correct
50	Correct	1234 ms	68132 KB	Output is correct
51	Correct	979 ms	58828 KB	Output is correct
52	Correct	847 ms	47544 KB	Output is correct
53	Correct	629 ms	40468 KB	Output is correct
54	Correct	489 ms	31872 KB	Output is correct
55	Correct	470 ms	31264 KB	Output is correct
56	Correct	453 ms	27640 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 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	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	8 ms	724 KB	Output is correct
28	Correct	6 ms	724 KB	Output is correct
29	Correct	8 ms	636 KB	Output is correct
30	Correct	6 ms	724 KB	Output is correct
31	Correct	8 ms	724 KB	Output is correct
32	Correct	6 ms	724 KB	Output is correct
33	Correct	8 ms	724 KB	Output is correct
34	Correct	7 ms	724 KB	Output is correct
35	Correct	47 ms	5880 KB	Output is correct
36	Correct	56 ms	6244 KB	Output is correct
37	Correct	47 ms	6180 KB	Output is correct
38	Correct	45 ms	6120 KB	Output is correct
39	Correct	45 ms	6236 KB	Output is correct
40	Correct	30 ms	3764 KB	Output is correct
41	Correct	31 ms	3696 KB	Output is correct
42	Correct	27 ms	3144 KB	Output is correct
43	Correct	26 ms	3068 KB	Output is correct
44	Correct	30 ms	3768 KB	Output is correct
45	Correct	30 ms	3800 KB	Output is correct
46	Correct	25 ms	3156 KB	Output is correct
47	Correct	25 ms	3028 KB	Output is correct
48	Correct	1200 ms	68028 KB	Output is correct
49	Correct	1208 ms	68032 KB	Output is correct
50	Correct	1234 ms	68132 KB	Output is correct
51	Correct	979 ms	58828 KB	Output is correct
52	Correct	847 ms	47544 KB	Output is correct
53	Correct	629 ms	40468 KB	Output is correct
54	Correct	489 ms	31872 KB	Output is correct
55	Correct	470 ms	31264 KB	Output is correct
56	Correct	453 ms	27640 KB	Output is correct
57	Execution timed out	2548 ms	81368 KB	Time limit exceeded
58	Halted	0 ms	0 KB	-

답안 #824656

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 30.0 / 30.0

Subtask #3 10.0 / 10.0

Subtask #4 25.0 / 25.0

Subtask #5 0 / 20.0

Subtask #1
15.0 / 15.0

Subtask #2
30.0 / 30.0

Subtask #3
10.0 / 10.0

Subtask #4
25.0 / 25.0

Subtask #5
0 / 20.0