답안 #745284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745284	2023-05-19T17:49:30 Z	speedyArda	화성 (APIO22_mars)	C++17	36 / 100	173 ms	3048 KB

mars

#include<bits/stdc++.h>
#include"mars.h"
using namespace std;
int const N=2333,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int f[N];
int find(int x){
	return f[x]^x?f[x]=find(f[x]):x;
}
void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx^fy)f[fx]=fy;
}
int ord(int x,int y,int n){
	return x*n+y;
}
string solve(vector<vector<string>>const&a,int n){
	string s=string(N,48);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int x=0;x<n/2;x++)
				for(int y=0;y<n/2;y++)
					s[ord(i+x*2,j+y*2,n)]=a[i][j][ord(x,y,n/2)];
	//rebuild the whole graph
	for(int i=0;i<n*n;i++)
		if(s[i]==49)f[i]=i;
	for(int x=0;x<n;x++)
		for(int y=0;y<n;y++)
			for(int i=0;i<4;i++){
				int tx=x+dx[i],ty=y+dy[i],p1=ord(x,y,n),p2=ord(tx,ty,n);
				if(tx<0||tx>=n||ty<0||ty>=n||s[p1]==48||s[p2]==48)continue;
				merge(p1,p2);
			}
	int cnt=0;
	for(int i=0;i<n*n;i++)
		cnt+=s[i]==49&&find(i)==i;
	//use dsu to count the answer
	string res=string(100,48);
	for(int i=0;cnt;i++)
		res[i]+=cnt&1,cnt>>=1;
	return res;
}
string process(vector<vector<string>>a,int ti,int tj,int k,int n){
	string s=string(100,48);
	if(k==n-1)
		return solve(a,2*n+1);
	for(int i=0;i<3;i+=2)
		for(int j=0;j<3;j+=2)
			for(int x=0;x<=k;x++)
				for(int y=0;y<=k;y++)
					s[ord(x+i/2,y+j/2,k+2)]=a[i][j][ord(x,y,k+1)];
	//(x,y) stores the info of (x+2i,y+2j) instead of (x+i,y+j) (i,j\in N)
	return s;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct

Subtask #4
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct
21	Correct	65 ms	2636 KB	Output is correct
22	Correct	86 ms	2724 KB	Output is correct
23	Correct	87 ms	2700 KB	Output is correct
24	Correct	88 ms	2720 KB	Output is correct
25	Correct	84 ms	2700 KB	Output is correct
26	Correct	89 ms	2892 KB	Output is correct
27	Correct	84 ms	2712 KB	Output is correct
28	Correct	82 ms	2708 KB	Output is correct

Subtask #5
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct
21	Correct	65 ms	2636 KB	Output is correct
22	Correct	86 ms	2724 KB	Output is correct
23	Correct	87 ms	2700 KB	Output is correct
24	Correct	88 ms	2720 KB	Output is correct
25	Correct	84 ms	2700 KB	Output is correct
26	Correct	89 ms	2892 KB	Output is correct
27	Correct	84 ms	2712 KB	Output is correct
28	Correct	82 ms	2708 KB	Output is correct
29	Correct	123 ms	2780 KB	Output is correct
30	Correct	164 ms	2868 KB	Output is correct
31	Correct	156 ms	3048 KB	Output is correct
32	Correct	160 ms	2956 KB	Output is correct
33	Correct	159 ms	2872 KB	Output is correct
34	Correct	162 ms	2860 KB	Output is correct
35	Correct	159 ms	2852 KB	Output is correct
36	Correct	173 ms	2952 KB	Output is correct

Subtask #6
0.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct
21	Correct	65 ms	2636 KB	Output is correct
22	Correct	86 ms	2724 KB	Output is correct
23	Correct	87 ms	2700 KB	Output is correct
24	Correct	88 ms	2720 KB	Output is correct
25	Correct	84 ms	2700 KB	Output is correct
26	Correct	89 ms	2892 KB	Output is correct
27	Correct	84 ms	2712 KB	Output is correct
28	Correct	82 ms	2708 KB	Output is correct
29	Correct	123 ms	2780 KB	Output is correct
30	Correct	164 ms	2868 KB	Output is correct
31	Correct	156 ms	3048 KB	Output is correct
32	Correct	160 ms	2956 KB	Output is correct
33	Correct	159 ms	2872 KB	Output is correct
34	Correct	162 ms	2860 KB	Output is correct
35	Correct	159 ms	2852 KB	Output is correct
36	Correct	173 ms	2952 KB	Output is correct
37	Runtime error	30 ms	636 KB	Execution killed with signal 6
38	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct
21	Correct	65 ms	2636 KB	Output is correct
22	Correct	86 ms	2724 KB	Output is correct
23	Correct	87 ms	2700 KB	Output is correct
24	Correct	88 ms	2720 KB	Output is correct
25	Correct	84 ms	2700 KB	Output is correct
26	Correct	89 ms	2892 KB	Output is correct
27	Correct	84 ms	2712 KB	Output is correct
28	Correct	82 ms	2708 KB	Output is correct
29	Correct	123 ms	2780 KB	Output is correct
30	Correct	164 ms	2868 KB	Output is correct
31	Correct	156 ms	3048 KB	Output is correct
32	Correct	160 ms	2956 KB	Output is correct
33	Correct	159 ms	2872 KB	Output is correct
34	Correct	162 ms	2860 KB	Output is correct
35	Correct	159 ms	2852 KB	Output is correct
36	Correct	173 ms	2952 KB	Output is correct
37	Runtime error	30 ms	636 KB	Execution killed with signal 6
38	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct
21	Correct	65 ms	2636 KB	Output is correct
22	Correct	86 ms	2724 KB	Output is correct
23	Correct	87 ms	2700 KB	Output is correct
24	Correct	88 ms	2720 KB	Output is correct
25	Correct	84 ms	2700 KB	Output is correct
26	Correct	89 ms	2892 KB	Output is correct
27	Correct	84 ms	2712 KB	Output is correct
28	Correct	82 ms	2708 KB	Output is correct
29	Correct	123 ms	2780 KB	Output is correct
30	Correct	164 ms	2868 KB	Output is correct
31	Correct	156 ms	3048 KB	Output is correct
32	Correct	160 ms	2956 KB	Output is correct
33	Correct	159 ms	2872 KB	Output is correct
34	Correct	162 ms	2860 KB	Output is correct
35	Correct	159 ms	2852 KB	Output is correct
36	Correct	173 ms	2952 KB	Output is correct
37	Runtime error	30 ms	636 KB	Execution killed with signal 6
38	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct
21	Correct	65 ms	2636 KB	Output is correct
22	Correct	86 ms	2724 KB	Output is correct
23	Correct	87 ms	2700 KB	Output is correct
24	Correct	88 ms	2720 KB	Output is correct
25	Correct	84 ms	2700 KB	Output is correct
26	Correct	89 ms	2892 KB	Output is correct
27	Correct	84 ms	2712 KB	Output is correct
28	Correct	82 ms	2708 KB	Output is correct
29	Correct	123 ms	2780 KB	Output is correct
30	Correct	164 ms	2868 KB	Output is correct
31	Correct	156 ms	3048 KB	Output is correct
32	Correct	160 ms	2956 KB	Output is correct
33	Correct	159 ms	2872 KB	Output is correct
34	Correct	162 ms	2860 KB	Output is correct
35	Correct	159 ms	2852 KB	Output is correct
36	Correct	173 ms	2952 KB	Output is correct
37	Runtime error	30 ms	636 KB	Execution killed with signal 6
38	Halted	0 ms	0 KB	-

Subtask #10
0.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2104 KB	Output is correct
2	Correct	8 ms	2036 KB	Output is correct
3	Correct	8 ms	2004 KB	Output is correct
4	Correct	8 ms	2296 KB	Output is correct
5	Correct	8 ms	2288 KB	Output is correct
6	Correct	8 ms	2200 KB	Output is correct
7	Correct	11 ms	1844 KB	Output is correct
8	Correct	16 ms	2004 KB	Output is correct
9	Correct	16 ms	2152 KB	Output is correct
10	Correct	16 ms	2220 KB	Output is correct
11	Correct	16 ms	1788 KB	Output is correct
12	Correct	16 ms	2012 KB	Output is correct
13	Correct	16 ms	2268 KB	Output is correct
14	Correct	30 ms	2660 KB	Output is correct
15	Correct	40 ms	2664 KB	Output is correct
16	Correct	41 ms	2664 KB	Output is correct
17	Correct	40 ms	2640 KB	Output is correct
18	Correct	40 ms	2668 KB	Output is correct
19	Correct	43 ms	2636 KB	Output is correct
20	Correct	41 ms	2608 KB	Output is correct
21	Correct	65 ms	2636 KB	Output is correct
22	Correct	86 ms	2724 KB	Output is correct
23	Correct	87 ms	2700 KB	Output is correct
24	Correct	88 ms	2720 KB	Output is correct
25	Correct	84 ms	2700 KB	Output is correct
26	Correct	89 ms	2892 KB	Output is correct
27	Correct	84 ms	2712 KB	Output is correct
28	Correct	82 ms	2708 KB	Output is correct
29	Correct	123 ms	2780 KB	Output is correct
30	Correct	164 ms	2868 KB	Output is correct
31	Correct	156 ms	3048 KB	Output is correct
32	Correct	160 ms	2956 KB	Output is correct
33	Correct	159 ms	2872 KB	Output is correct
34	Correct	162 ms	2860 KB	Output is correct
35	Correct	159 ms	2852 KB	Output is correct
36	Correct	173 ms	2952 KB	Output is correct
37	Runtime error	30 ms	636 KB	Execution killed with signal 6
38	Halted	0 ms	0 KB	-

답안 #745284

Compilation message