oj.uz

Submission #969733

# Submission time Handle Problem Language Result Execution time Memory
969733 2024-04-25T14:09:17 Z anton Mars (APIO22_mars) C++17
14 / 100
 13 ms 4700 KB 
#include "mars.h"
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define x real()
#define y imag()
#define point complex<int>

int to_id(int i, int j, int sz){
	return i*sz + j;
}
string reconstruct(vector<vector<string>>& a, int k){
	int prev_sz = (2*k + 1)*(2*k+1);
	int side_sz = 2*k+1;
	vector<string> res(2*k+3);
	for(int i = 0; i<side_sz; i++){
		for(int j = 0; j<side_sz; j++){
			res[i].push_back(a[0][0][i*side_sz + j]);
		}
	}

	for(int j = 0; j<2; j++){
		for(int i = 0; i<side_sz; i++){
			res[side_sz+j].push_back(a[2][0][to_id(side_sz-2+j, i, side_sz)]);
		}
	}
	
	for(int i = 0; i<side_sz; i++){
		for(int j = 0; j<2; j++){
			res[i].push_back(a[0][2][to_id(i, side_sz-2+j, side_sz)]);
		}
	}

	for(int i= 0; i<2; i++){
		for(int j = 0; j<2; j++){
			res[i+side_sz].push_back(a[2][2][to_id(side_sz-2+i, side_sz-2+j, side_sz)]);
		}
	}

	string r;
	for(auto e: res){
		//cout<<e<<endl;
		r.append(e.begin(), e.end());
	}
	while(r.size()<100){
		r.push_back('0');
	}
	return r;
}

string base(vector<vector<string>>& v){
	string res;
	for(int i = 0; i<3; i++){
		for(int j = 0; j<3; j++){
			res.push_back(v[i][j][0]);
		}
	}

	while(res.size()<100){
		res.push_back('0');
	}
	return res;
}

void dfs(string& readable, point pos, vector<vector<bool>>& vis, int h){
	vis[pos.x][pos.y] = true;
	
	vector<point> d = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
	for(auto e: d){
		point np = pos + e;
		if(np.x>=0 && np.x<h){
			if(np.y>=0 && np.y<h){
				if(!vis[np.x][np.y]){
					if(readable[to_id(np.x, np.y, h)] == '1'){
						dfs(readable, np, vis, h);
					}
				}
			}
		}
	}
}

int count_components(vector<vector<string>>&a, int k){
	string readable;
	if(k != 0){
		readable = reconstruct(a, k);
	}
	else{
		readable = base(a);
	}
	int h = (2*k+3);
	vector<vector<bool>> vis(h, vector<bool>(h));

	
	int res=  0;
	for(int i = 0; i<h; i++){
		for(int j = 0; j<h; j++){
			if(!vis[i][j]){
				if(readable[to_id(i, j, h)] == '1'){
					res++;
					dfs(readable, {i, j}, vis, h);
				}
			}
		}
	}
	return res;
}



string to_str(int v){
	string res(100, '0');
	for(int i = 0; i<20; i++){
		if(v & (1<<i)){
			res[i] = '1';
		}
	}
	return res;
}



std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
	
	if(k == n-1){
		return to_str(count_components(a, k));
	}
	else if(k == 0){
		return base(a);
	}
	else{
		return reconstruct(a,k);
	}
}

Compilation message

mars.cpp: In function 'std::string reconstruct(std::vector<std::vector<std::__cxx11::basic_string<char> > >&, int)':
mars.cpp:14:6: warning: unused variable 'prev_sz' [-Wunused-variable]
   14 |  int prev_sz = (2*k + 1)*(2*k+1);
      |      ^~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3704 KB Output is correct
2 Correct 6 ms 4208 KB Output is correct
3 Correct 7 ms 3620 KB Output is correct
4 Correct 5 ms 3688 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 7 ms 4128 KB Output is correct
7 Correct 8 ms 3872 KB Output is correct
8 Correct 9 ms 3984 KB Output is correct
9 Correct 9 ms 4700 KB Output is correct
10 Correct 13 ms 4444 KB Output is correct
11 Correct 8 ms 4144 KB Output is correct
12 Correct 9 ms 3620 KB Output is correct
13 Correct 11 ms 4040 KB Output is correct
14 Incorrect 2 ms 448 KB invalid len
15 Halted 0 ms 0 KB -