oj.uz

Submission #745284

# Submission time Handle Problem Language Result Execution time Memory
745284 2023-05-19T17:49:30 Z speedyArda Mars (APIO22_mars) C++17
36 / 100
 173 ms 3048 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -