Submission #648115

#	Time	Username	Problem	Language	Result	Execution time	Memory
648115		US3RN4M3	Mars (APIO22_mars)	C++17	0 / 100	1 ms	200 KiB

mars

#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
/* format for the data structures:
 * non-diagonal square:
 * =======================================================================================================
 * |         bits 0-49: current column/row            |        bits 50-99: adjacent column/row           |
 * =======================================================================================================
 * 
 * diagonal square:
 * =======================================================================================================
 * |   bits 0-9: number of islands |                    bits 10-99: group information                    |
 * =======================================================================================================
 */
void form_group_information(vector<int> tile_ids, string & output) {
	map<int, int> firsts;
	map<int, int> lasts;
	for(int i = 0; i < tile_ids.size(); i++) {
		if(!tile_ids[i]) continue;
		if(!firsts.count(tile_ids[i])) firsts[tile_ids[i]] = i;
		lasts[tile_ids[i]] = i;
	}
	for(auto & [k,v] : firsts) output[10 + v] = '1';
	for(auto & [k,v] : lasts) output[11 + v] = '1';
}
string process(vector<vector<string>> adjacent, int cur_x, int cur_y, int iteration, int size)
{
	string ret(100, '0');
	if(cur_y == 2 * (size-iteration - 1) && cur_x == 2 * (size-iteration - 1)) {
		if(iteration==0) {
			int grid[3][3] = {0};
			bool vis[3][3] = {false};
			function<void(int,int)> dfs = [&](int stt_x, int stt_y) {
				vis[stt_x][stt_y] = true;
				if(stt_x > 0 && grid[stt_x - 1][stt_y] == 1 && !vis[stt_x - 1][stt_y]) {
					grid[stt_x - 1][stt_y] = grid[stt_x][stt_y];
					dfs(stt_x - 1, stt_y);
				}
				if(stt_y > 0 && grid[stt_x][stt_y - 1] == 1 && !vis[stt_x][stt_y - 1]) {
					grid[stt_x][stt_y - 1] = grid[stt_x][stt_y];
					dfs(stt_x, stt_y - 1);
				}
				if(stt_x < 2 && grid[stt_x + 1][stt_y] == 1 && !vis[stt_x + 1][stt_y]) {
					grid[stt_x + 1][stt_y] = grid[stt_x][stt_y];
					dfs(stt_x + 1, stt_y);
				}
				if(stt_y < 2 && grid[stt_x][stt_y + 1] == 1 && !vis[stt_x][stt_y + 1]) {
					grid[stt_x][stt_y + 1] = grid[stt_x][stt_y];
					dfs(stt_x, stt_y + 1);
				}
			};
			for(int i = 0; i < 9; i++) {
				if(adjacent[i/3][i%3][0]=='1') grid[i/3][i%3] = 1;
			}
			int max_id = 9;
			int num_islands = 0;
			for(int i = 0; i < 9; i++) {
				if(grid[i%3][i/3] && !vis[i%3][i/3]) {
					grid[i%3][i/3] = max_id++;
					num_islands++;
					dfs(i%3, i/3);
				}
			}
			vector<int> v{grid[2][0], grid[1][0], grid[0][0], grid[0][1], grid[0][2]};
			form_group_information(v, ret);
			ret[0] = '0';
			if(num_islands&1) ret[0] = '1';
			if(num_islands&2) ret[1] = '1';
			if(num_islands&4) ret[2] = '1';
			return ret;
		}
		int grid[50][50] = {0};
		bool vis[50][50] = {false};
		int num_islands = 0;
		string & prev = adjacent[2][2];
		for(int i = 0; i < 10; i++) {
			if(prev[i] == '1') num_islands += 1<<i;
		}
		for(int i = 2 * size; i > cur_x + 1; i--) {
			if(adjacent[2][0][i - cur_x - 2] == '1') grid[i][cur_x] = 1;
			if(adjacent[0][2][i - cur_x - 2] == '1') grid[cur_x][i] = 1;
			if(adjacent[2][0][i - cur_x - 2 + 50] == '1') grid[i][cur_x+1] = 1;
			if(adjacent[0][2][i - cur_x - 2 + 50] == '1') grid[cur_x+1][i] = 1;
			if(adjacent[2][1][i - cur_x - 2 + 50] == '1') grid[i][cur_x+2] = 1;
			if(adjacent[1][2][i - cur_x - 2 + 50] == '1') grid[cur_x+2][i] = 1;
		}
		if(adjacent[0][0][0] == '1') grid[cur_x][cur_x] = 1;
		if(adjacent[0][1][0] == '1') grid[cur_x][cur_x + 1] = 1;
		if(adjacent[1][0][0] == '1') grid[cur_x + 1][cur_x] = 1;
		if(adjacent[1][1][0] == '1') grid[cur_x + 1][cur_x + 1] = 1;
		int max_id = 2;
		int cur_id = 2;
		stack<int> prev_ids;
		int x = 2 * size, y = cur_x + 2;
		bool direction = false;
		for(int i = 0; i < iteration * 4 + 1; i++) {
			if(x == cur_x + 2 && y == cur_x + 2) direction = true;
			if(prev[i + 10] == '1') {
				if(grid[x][y]) {
					prev_ids.push(cur_id);
					cur_id = ++max_id;
				} else {
					cur_id = prev_ids.top();
					prev_ids.pop();
				}
			}
			if(grid[x][y]) grid[x][y] = cur_id;
			if(direction) y++;
			else x--;
		}
		function<void(int,int)> replace = [&] (int x, int y) {
			for(int i = 0; i <= 2*size; i++) for(int j = 0; j <= 2*size; j++) {
				if(grid[i][j] == x) grid[i][j] = y;
			}
		};
		function<void(int,int,int)> dfs = [&] (int x, int y, int p) {
			if(vis[x][y] || !grid[x][y]) return;
			vis[x][y] = true;
			if(grid[x][y] == 1) grid[x][y] = p;
			if(grid[x][y]!=p) {
				replace(p, grid[x][y]);
				num_islands--;
			}
			if(x > 0) dfs(x-1, y, grid[x][y]);
			if(y > 0) dfs(x, y-1, grid[x][y]);
			if(x < 2*size) dfs(x+1, y, grid[x][y]);
			if(y < 2*size) dfs(x,y+1, grid[x][y]);
		};
		for(int i = 0; i <= 2*size; i++) for(int j = 0; j <= 2*size; j++) if(grid[i][j] != 1) dfs(i, j, grid[i][j]);
		for(int i = 0; i <= 2*size; i++) for(int j = 0; j <= 2*size; j++) if(grid[i][j] == 1) {
			grid[i][j] = ++max_id;
			num_islands++;
			dfs(i, j, grid[i][j]);
		}
		x = 2 * size;
		y = cur_x;
		vector<int> border_ids;
		direction = false;
		for(int i = 0; i < iteration * 4 + 5; i++) {
			if(x == cur_x && y == cur_x) direction = true;
			border_ids.push_back(grid[x][y]);
			if(direction) y++;
			else x--;
		}
		for(int i = 0; i < 10; i++) {
			if((num_islands>>i)&1) ret[i] = '1';
		}
		if(iteration != size - 1) form_group_information(border_ids, ret);
	}
	else if(cur_x == 2 * (size-iteration - 1)) {
		ret[0] = adjacent[0][0][0];
		ret[1] = adjacent[1][0][0];
		ret[50] = adjacent[0][1][0];
		ret[51] = adjacent[1][1][0];
		for(int i = 2; i < 50; i++) {
			if(adjacent[2][0][i - 2] == '1') ret[i] = '1';
			if(adjacent[2][1][i - 2] == '1') ret[i + 50] = '1';
		}
	} 
	else if(cur_y == 2 * (size-iteration - 1)) {
		ret[0] = adjacent[0][0][0];
		ret[1] = adjacent[0][1][0];
		ret[50] = adjacent[1][0][0];
		ret[51] = adjacent[1][1][0];
		for(int i = 2; i < 50; i++) {
			if(adjacent[0][2][i - 2] == '1') ret[i] = '1';
			if(adjacent[1][2][i - 2] == '1') ret[i + 50] = '1';
		}
	} else ret = adjacent[0][0];
	return ret;
}

Compilation message (stderr)

mars.cpp: In function 'void form_group_information(std::vector<int>, std::string&)':
mars.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0; i < tile_ids.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 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