Submission #969733

#	Time	Username	Problem	Language	Result	Execution time	Memory
969733		anton	Mars (APIO22_mars)	C++17	14 / 100	13 ms	4700 KiB

mars

#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 (stderr)

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 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11