| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 575932 |
2022-06-11T21:36:53 Z |
SHZhang |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
200 KB |
#include "mars.h"
#include <utility>
#include <set>
using namespace std;
// on phase k, preexisting size 2 * k + 1
// row, col
// even, even: comp # (11 bits), bot up, bot down, right left, right right,
// perimeter blocks (up to 80)
// even, odd: bottom region, first top row, then bottom row
// odd, even: right region, first left col, then right col
#define encode(r, c) ((r) * (2 * k + 3) + (c))
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int fin(int* uf, int x)
{
if (uf[x] == x) return x;
return uf[x] = fin(uf, uf[x]);
}
void un(int* uf, int x, int y)
{
x = fin(uf, x);
y = fin(uf, y);
uf[x] = y;
}
string process(vector <vector<string>> a, int x, int y, int k, int n)
{
(void)n;
string ans = string(100, '0');
if (x % 2 == 1 && y % 2 == 1) return ans;
if (k == 0) {
if (x % 2 == 0 && y % 2 == 1) {
ans[0] = a[1][0][0];
ans[1] = a[1][1][0];
ans[2] = a[2][0][0];
ans[3] = a[2][1][0];
} else if (x % 2 == 1 && y % 2 == 0) {
ans[0] = a[0][1][0];
ans[1] = a[1][1][0];
ans[2] = a[0][2][0];
ans[3] = a[1][2][0];
} else {
ans[11] = a[1][0][0];
ans[12] = a[2][0][0];
ans[13] = a[0][1][0];
ans[14] = a[0][2][0];
ans[96] = a[1][1][0];
ans[97] = a[1][2][0];
ans[98] = a[2][1][0];
ans[99] = a[2][2][0];
int uf[9];
for (int i = 0; i < 9; i++) uf[i] = i;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (a[i][j][0] == '0') continue;
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni < 0 || ni >= 3 || nj < 0 || nj >= 3) continue;
if (a[ni][nj][0] == '1') un(uf, encode(i, j), encode(ni, nj));
}
}
}
int compcnt = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (a[i][j][0] == '0') continue;
if (fin(uf, encode(i, j)) == encode(i, j)) compcnt++;
}
}
for (int i = 0; i < 11; i++) {
if (compcnt & (1 << i)) {
ans[i] = '1';
} else {
ans[i] = '0';
}
}
vector<pair<int, int> > botright1;
for (int i = 0; i <= 2 * k + 2; i++) botright1.push_back(make_pair(2 * k, i));
for (int i = 2 * k + 1; i >= 0; i--) botright1.push_back(make_pair(i, 2 * k));
vector<int> botright;
for (int i = 0; i < botright1.size(); i++) {
if (a[botright1[i].first][botright1[i].second][0] == '1' &&
(i == 0 || a[botright1[i-1].first][botright1[i-1].second][0] == '0')) {
botright.push_back(encode(botright1[i].first, botright1[i].second));
}
}
for (int i = 0; i < botright.size(); i++) {
bool has_before = false;
bool has_after = false;
for (int j = 0; j < i; j++) {
if (fin(uf, botright[i]) == fin(uf, botright[j])) has_before = true;
}
for (int j = i + 1; j < botright.size(); j++) {
if (fin(uf, botright[i]) == fin(uf, botright[j])) has_after = true;
}
if (!has_before && !has_after) {
ans[15 + 2*i] = '0';
ans[16 + 2*i] = '0';
} else if (has_before && !has_after) {
// last
ans[15 + 2*i] = '1';
ans[16 + 2*i] = '1';
} else if (!has_before && has_after) {
// first
ans[15 + 2*i] = '0';
ans[16 + 2*i] = '1';
} else {
ans[15 + 2*i] = '1';
ans[16 + 2*i] = '0';
}
}
}
if (k == n - 1) {
for (int i = 11; i < 100; i++) ans[i] = '0';
}
return ans;
}
if (x % 2 == 0 && y % 2 == 1) {
for (int i = 0; i < 2 * k; i++) {
ans[i] = a[2][0][i];
ans[i + 2*k + 2] = a[2][0][2*k+i];
}
for (int i = 0; i < 2 * k; i++) {
ans[i + 2] = a[2][2][i];
ans[i + 2*k + 4] = a[2][2][2*k+i];
}
} else if (x % 2 == 1 && y % 2 == 0) {
for (int i = 0; i < 2 * k; i++) {
ans[i] = a[0][2][i];
ans[i + 2*k + 2] = a[0][2][2*k+i];
}
for (int i = 0; i < 2 * k; i++) {
ans[i + 2] = a[2][2][i];
ans[i + 2*k + 4] = a[2][2][2*k+i];
}
} else {
int* uf = new int[(2 * k + 3) * (2 * k + 3)];
bool* outer_comp = new bool[(2 * k + 3) * (2 * k + 3)];
for (int i = 0; i < (2 * k + 3) * (2 * k + 3); i++) {
uf[i] = i; outer_comp[i] = true;
}
bool* land[45];
for (int i = 0; i < 45; i++) {
land[i] = new bool[45];
}
for (int i = 0; i < (2 * k + 3); i++) {
for (int j = 0; j < (2 * k + 3); j++) {
land[i][j] = false;
}
}
for (int i = 0; i < 2 * k; i++) {
land[2 * k - 1][i + 1] = (a[0][1][i] == '1');
land[2 * k][i + 1] = (a[0][1][2 * k + i] == '1');
land[2 * k + 1][i + 1] = (a[2][1][i] == '1');
land[2 * k + 2][i + 1] = (a[2][1][2 * k + i] == '1');
land[i + 1][2 * k - 1] = (a[1][0][i] == '1');
land[i + 1][2 * k] = (a[1][0][2 * k + i] == '1');
land[i + 1][2 * k + 1] = (a[1][2][i] == '1');
land[i + 1][2 * k + 2] = (a[1][2][2 * k + i] == '1');
}
//fprintf(stderr, "! %d %c %c %c %c\n", k, a[0][0][11], a[0][0][12], a[0][0][13], a[0][0][14]);
land[2 * k - 1][0] = (a[0][0][11] == '1');
land[2 * k][0] = (a[0][0][12] == '1');
land[2 * k + 1][0] = (a[2][0][11] == '1');
land[2 * k + 2][0] = (a[2][0][12] == '1');
land[0][2 * k - 1] = (a[0][0][13] == '1');
land[0][2 * k] = (a[0][0][14] == '1');
land[0][2 * k + 1] = (a[0][2][13] == '1');
land[0][2 * k + 2] = (a[0][2][14] == '1');
land[2 * k + 1][2 * k + 1] = (a[2][2][96] == '1');
land[2 * k + 1][2 * k + 2] = (a[2][2][97] == '1');
land[2 * k + 2][2 * k + 1] = (a[2][2][98] == '1');
land[2 * k + 2][2 * k + 2] = (a[2][2][99] == '1');
//fprintf(stderr, "%d %d %d\n", x, y, k);
for (int i = 0; i <= 2 * k + 2; i++) {
for (int j = 0; j <= 2 * k + 2; j++) {
//fprintf(stderr, "%d", (int)land[i][j]);
}
//fprintf(stderr, "\n");
}
ans[11] = a[2][0][11];
ans[12] = a[2][0][12];
ans[13] = a[0][2][13];
ans[14] = a[0][2][14];
ans[96] = a[2][2][96];
ans[97] = a[2][2][97];
ans[98] = a[2][2][98];
ans[99] = a[2][2][99];
vector<pair<int, int> > botright1;
for (int i = 0; i <= 2 * k; i++) botright1.push_back(make_pair(2 * k, i));
for (int i = 2 * k - 1; i >= 0; i--) botright1.push_back(make_pair(i, 2 * k));
vector<int> botright;
for (int i = 0; i < botright1.size(); i++) {
if (land[botright1[i].first][botright1[i].second] &&
(i == 0 || !land[botright1[i-1].first][botright1[i-1].second])) {
botright.push_back(encode(botright1[i].first, botright1[i].second));
}
}
vector<int> stk;
for (int i = 0; i < botright.size(); i++) {
if (a[0][0][15 + 2*i] == '0' && a[0][0][16 + 2*i] == '0') {
// only element in comp
} else if (a[0][0][15 + 2*i] == '0' && a[0][0][16 + 2*i] == '1') {
// first element in comp
stk.push_back(botright[i]);
} else if (a[0][0][15 + 2*i] == '1' && a[0][0][16 + 2*i] == '0') {
// middle element in comp
un(uf, stk.back(), botright[i]);
} else if (a[0][0][15 + 2*i] == '1' && a[0][0][16 + 2*i] == '1') {
// last element in comp
un(uf, stk.back(), botright[i]);
stk.pop_back();
}
}
for (int i = 0; i < 2 * k + 1; i++) {
for (int j = 0; j < 2 * k + 1; j++) {
if (!land[i][j]) continue;
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni < 0 || ni >= 2 * k + 1 || nj < 0 || nj >= 2 * k + 1) continue;
if (land[ni][nj]) un(uf, encode(i, j), encode(ni, nj));
}
}
}
set<int> old_bound_comps;
for (int i = 0; i < botright.size(); i++) {
old_bound_comps.insert(fin(uf, botright[i]));
}
for (int i = 0; i < 2 * k + 3; i++) {
for (int j = 0; j < 2 * k + 3; j++) {
if (!land[i][j]) continue;
for (int d = 0; d < 4; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (ni < 0 || ni >= 2 * k + 3 || nj < 0 || nj >= 2 * k + 3) continue;
if (land[ni][nj]) un(uf, encode(i, j), encode(ni, nj));
}
}
}
set<int> new_bound_comps;
for (int i = 0; i < botright.size(); i++) {
new_bound_comps.insert(fin(uf, botright[i]));
}
int compcnt = (int)new_bound_comps.size() - (int)old_bound_comps.size();
for (int i = 0; i < 11; i++) {
if (a[0][0][i] == '1') compcnt += (1 << i);
}
for (int i = 0; i < 2 * k + 1; i++) {
for (int j = 0; j < 2 * k + 1; j++) {
if (!land[i][j]) continue;
outer_comp[fin(uf, encode(i, j))] = false;
}
}
for (int i = 0; i < 2 * k + 3; i++) {
for (int j = 0; j < 2 * k + 3; j++) {
if (!land[i][j]) continue;
if (fin(uf, encode(i, j)) == encode(i, j) && outer_comp[encode(i, j)]) compcnt++;
}
}
for (int i = 0; i < 11; i++) {
if (compcnt & (1 << i)) {
ans[i] = '1';
} else {
ans[i] = '0';
}
}
botright1.clear();
for (int i = 0; i <= 2 * k + 2; i++) botright1.push_back(make_pair(2 * k, i));
for (int i = 2 * k + 1; i >= 0; i--) botright1.push_back(make_pair(i, 2 * k));
botright.clear();
for (int i = 0; i < botright1.size(); i++) {
if (land[botright1[i].first][botright1[i].second] &&
(i == 0 || !land[botright1[i-1].first][botright1[i-1].second])) {
botright.push_back(encode(botright1[i].first, botright1[i].second));
}
}
for (int i = 0; i < botright.size(); i++) {
bool has_before = false;
bool has_after = false;
for (int j = 0; j < i; j++) {
if (fin(uf, botright[i]) == fin(uf, botright[j])) has_before = true;
}
for (int j = i + 1; j < botright.size(); j++) {
if (fin(uf, botright[i]) == fin(uf, botright[j])) has_after = true;
}
if (!has_before && !has_after) {
ans[15 + 2*i] = '0';
ans[16 + 2*i] = '0';
} else if (has_before && !has_after) {
// last
ans[15 + 2*i] = '1';
ans[16 + 2*i] = '1';
} else if (!has_before && has_after) {
// first
ans[15 + 2*i] = '0';
ans[16 + 2*i] = '1';
} else {
ans[15 + 2*i] = '1';
ans[16 + 2*i] = '0';
}
}
fprintf(stderr, "! %d\n", compcnt);
delete[] uf;
delete[] outer_comp;
for (int i = 0; i < 45; i++) {
delete[] land[i];
}
}
if (k == n - 1) {
for (int i = 11; i < 100; i++) ans[i] = '0';
}
return ans;
}
Compilation message
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < botright1.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
mars.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 0; i < botright.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
mars.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int j = i + 1; j < botright.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
mars.cpp:200:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int i = 0; i < botright1.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
mars.cpp:207:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for (int i = 0; i < botright.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
mars.cpp:234:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
234 | for (int i = 0; i < botright.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
mars.cpp:249:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | for (int i = 0; i < botright.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
mars.cpp:279:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
279 | for (int i = 0; i < botright1.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
mars.cpp:285:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
285 | for (int i = 0; i < botright.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
mars.cpp:291:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
291 | for (int j = i + 1; j < botright.size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
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 |
- |
