oj.uz

답안 #974853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974853 2024-05-04T02:18:43 Z oolimry 화성 (APIO22_mars) C++17
14 / 100
 20 ms 4436 KB 
#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;

/// 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);
}


///attempt 1: each position be a bit in the 100 bit string
///we can store up to 100 bits, so a 9x9 grid max --> 14 points i think

int cellToBit(int i, int j){
	return (i) * 10 + j;
}

ii bitToCell(int b){
	return {b / 10, b % 10};
}

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++){
			for(int j = 0;j <= 2;j++){
				int pos = cellToBit(i+I, j+J);
				
				if(a[i][j][0] == '1') res[pos] = '1';
			}
		}
	}
	else{
		for(int i = 0;i <= 2;i++){
			for(int j = 0;j <= 2;j++){
				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;
		
		///fill in stuff
		for(int p = 0;p < 100;p++){
			if(res[p] == '1'){
				ii cell = bitToCell(p);
				int i = cell.first, j = cell.second;
				
				grid[i][j] = 1;
			}
		}
		
		///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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3856 KB Output is correct
2 Correct 8 ms 3832 KB Output is correct
3 Correct 8 ms 4336 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct
5 Correct 7 ms 4172 KB Output is correct
6 Correct 7 ms 4436 KB Output is correct
7 Correct 12 ms 4200 KB Output is correct
8 Correct 20 ms 4352 KB Output is correct
9 Correct 16 ms 4272 KB Output is correct
10 Correct 17 ms 4360 KB Output is correct
11 Correct 19 ms 3992 KB Output is correct
12 Correct 16 ms 3808 KB Output is correct
13 Correct 17 ms 4172 KB Output is correct
14 Runtime error 1 ms 420 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -