Submission #974862

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
974862	2024-05-04T02:59:43 Z	oolimry	Mars (APIO22_mars)	C++17	29 / 100	81 ms	4760 KB

mars

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define showlist(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
typedef pair<int,int> ii;
 
///attempt 2: each position be a bit in the 100 bit string
///but we store only for the positions (i mod 2) (j mod 2) - 4 color checkboard
///we can store up to 400 bits, so a 19x19 grid max --> 29 points i think
///probably if you ignore some cells you can optimize to 21x21

/// stuff for dfs
int grid[45][45];

void dfs(int i, int j){
	if(i < 0 or j < 0) return;
	if(grid[i][j] == 0) return;
	
	grid[i][j] = 0;
	
	dfs(i+1,j);
	dfs(i-1,j);
	dfs(i,j+1);
	dfs(i,j-1);
}

int cellToBit(int i, int j){
	return (i/2) * 10 + (j/2);
}
 
 
string process(vector <vector<string>> a, int I, int J, int K, int n){
	
	//cerr << I << " " << J << " " << K << endl;	
	
	string res = string(100 ,'0');
	
	if(K == 0){ ///first run
		for(int i = 0;i <= 2;i += 2){
			for(int j = 0;j <= 2;j += 2){
				int pos = cellToBit(i+I, j+J);
				
				if(a[i][j][0] == '1') res[pos] = '1';
			}
		}
	}
	else{
		for(int i = 0;i <= 2;i += 2){ ///+=2 for same color
			for(int j = 0;j <= 2;j += 2){
				for(int p = 0;p < 100;p++){
					if(a[i][j][p] == '1') res[p] = '1';
				}
			}
		}
	}
	
	
	if(K == n-1){ ///last phase --> convert to binary 
		for(int i = 0;i < 45;i++) for(int j = 0;j < 45;j++) grid[i][j] = 0;
		
		if(n == 1){ ///annoying edge case
			for(int i = 0;i <= 2;i++){
				for(int j = 0;j <= 2;j++){
					if(a[i][j][0] == '1') grid[i][j] = 1;
				}
			}
		}
		else{
			for(int io = 0;io <= 2;io += 1){
				for(int jo = 0;jo <= 2;jo += 1){
					for(int p = 0;p < 100;p++){
						if(a[io][jo][p] == '1'){
							int i = (p / 10) *  2 + (io % 2);
							int j = (p % 10) * 2 + (jo % 2);
							
							grid[i][j] = 1;
						}
					}
				}
			}
		}
		
		for(int i = 0;i < 2*n+1;i++){
			for(int j = 0;j < 2*n+1;j++) cerr << grid[i][j];
			cerr << endl;
		}
		
		///count no. of connected components via dfs
		int cnt = 0; 
		for(int i = 0;i < 45;i++) for(int j = 0;j < 45;j++){
			if(grid[i][j]){
				cnt++;
				dfs(i,j);
			}
		}
		
		//cerr << cnt << endl;
 
		res = string(100 ,'0');
		for(int p = 0;p < 100;p++){
			if(cnt % 2 == 1) res[p] = '1';
			cnt /= 2;
		}
	}
	
	//cerr << res << endl;
	
	return res;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct
21	Correct	41 ms	4684 KB	Output is correct
22	Correct	57 ms	4364 KB	Output is correct
23	Correct	59 ms	4144 KB	Output is correct
24	Correct	58 ms	4644 KB	Output is correct
25	Correct	58 ms	4236 KB	Output is correct
26	Correct	61 ms	3924 KB	Output is correct
27	Correct	58 ms	4688 KB	Output is correct
28	Correct	60 ms	4184 KB	Output is correct

Subtask #5
0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct
21	Correct	41 ms	4684 KB	Output is correct
22	Correct	57 ms	4364 KB	Output is correct
23	Correct	59 ms	4144 KB	Output is correct
24	Correct	58 ms	4644 KB	Output is correct
25	Correct	58 ms	4236 KB	Output is correct
26	Correct	61 ms	3924 KB	Output is correct
27	Correct	58 ms	4688 KB	Output is correct
28	Correct	60 ms	4184 KB	Output is correct
29	Correct	81 ms	4200 KB	Output is correct
30	Runtime error	3 ms	496 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct
21	Correct	41 ms	4684 KB	Output is correct
22	Correct	57 ms	4364 KB	Output is correct
23	Correct	59 ms	4144 KB	Output is correct
24	Correct	58 ms	4644 KB	Output is correct
25	Correct	58 ms	4236 KB	Output is correct
26	Correct	61 ms	3924 KB	Output is correct
27	Correct	58 ms	4688 KB	Output is correct
28	Correct	60 ms	4184 KB	Output is correct
29	Correct	81 ms	4200 KB	Output is correct
30	Runtime error	3 ms	496 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct
21	Correct	41 ms	4684 KB	Output is correct
22	Correct	57 ms	4364 KB	Output is correct
23	Correct	59 ms	4144 KB	Output is correct
24	Correct	58 ms	4644 KB	Output is correct
25	Correct	58 ms	4236 KB	Output is correct
26	Correct	61 ms	3924 KB	Output is correct
27	Correct	58 ms	4688 KB	Output is correct
28	Correct	60 ms	4184 KB	Output is correct
29	Correct	81 ms	4200 KB	Output is correct
30	Runtime error	3 ms	496 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct
21	Correct	41 ms	4684 KB	Output is correct
22	Correct	57 ms	4364 KB	Output is correct
23	Correct	59 ms	4144 KB	Output is correct
24	Correct	58 ms	4644 KB	Output is correct
25	Correct	58 ms	4236 KB	Output is correct
26	Correct	61 ms	3924 KB	Output is correct
27	Correct	58 ms	4688 KB	Output is correct
28	Correct	60 ms	4184 KB	Output is correct
29	Correct	81 ms	4200 KB	Output is correct
30	Runtime error	3 ms	496 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct
21	Correct	41 ms	4684 KB	Output is correct
22	Correct	57 ms	4364 KB	Output is correct
23	Correct	59 ms	4144 KB	Output is correct
24	Correct	58 ms	4644 KB	Output is correct
25	Correct	58 ms	4236 KB	Output is correct
26	Correct	61 ms	3924 KB	Output is correct
27	Correct	58 ms	4688 KB	Output is correct
28	Correct	60 ms	4184 KB	Output is correct
29	Correct	81 ms	4200 KB	Output is correct
30	Runtime error	3 ms	496 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Subtask #10
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3600 KB	Output is correct
2	Correct	5 ms	3372 KB	Output is correct
3	Correct	7 ms	3952 KB	Output is correct
4	Correct	7 ms	3792 KB	Output is correct
5	Correct	7 ms	4372 KB	Output is correct
6	Correct	7 ms	4036 KB	Output is correct
7	Correct	8 ms	4276 KB	Output is correct
8	Correct	11 ms	4028 KB	Output is correct
9	Correct	9 ms	3984 KB	Output is correct
10	Correct	8 ms	4344 KB	Output is correct
11	Correct	9 ms	4324 KB	Output is correct
12	Correct	8 ms	4200 KB	Output is correct
13	Correct	8 ms	4028 KB	Output is correct
14	Correct	18 ms	4072 KB	Output is correct
15	Correct	24 ms	4196 KB	Output is correct
16	Correct	23 ms	3724 KB	Output is correct
17	Correct	27 ms	4248 KB	Output is correct
18	Correct	26 ms	4736 KB	Output is correct
19	Correct	24 ms	4760 KB	Output is correct
20	Correct	28 ms	4156 KB	Output is correct
21	Correct	41 ms	4684 KB	Output is correct
22	Correct	57 ms	4364 KB	Output is correct
23	Correct	59 ms	4144 KB	Output is correct
24	Correct	58 ms	4644 KB	Output is correct
25	Correct	58 ms	4236 KB	Output is correct
26	Correct	61 ms	3924 KB	Output is correct
27	Correct	58 ms	4688 KB	Output is correct
28	Correct	60 ms	4184 KB	Output is correct
29	Correct	81 ms	4200 KB	Output is correct
30	Runtime error	3 ms	496 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Submission #974862

Compilation message