| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 648115 |
2022-10-05T12:08:17 Z |
US3RN4M3 |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
200 KB |
#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
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++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
