#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
bool val(string &s, int p = 0) {
return s[p]-'0';
}
int find(int i, vector<int> &uf) {
return uf[i] == i ? i : uf[i] = find(uf[i], uf);
}
void merge(int a, int b, vector<int> &uf) {
a = find(a, uf);
b = find(b, uf);
if (a != b) uf[a] = b;
}
/*
BIT ALLOCATION:
For main diag, first bit is for value,
next 44 bits are for start and then end union find when starting from the bottom,
going up, and then right
last 10 bits are for the answer
For off diag, first 50 bits represent going down/right,
and next 50 bits are down/right one row/column over
*/
string process(vector<vector<string>> visible, int i, int j, int k, int n) {
if (i < 2*(n-k-1) && j < 2*(n-k-1)) return visible[0][0];
int m = 2*k+3;
if (i == j) {
if (i & 1) return visible[0][0];
bool **grid;
grid = new bool*[m];
for (int a = 0; a < m; a++) {
grid[a] = new bool[m];
fill(grid[a], grid[a]+m, 0);
} // make the grid
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 3; b++)
grid[a][b] = val(visible[a][b]);
}
for (int b = 2; b < m; b++) {
grid[b][0] = val(visible[2][0], b-2);
grid[b][1] = val(visible[2][1], b-2);
grid[b][2] = val(visible[2][1], 50+b-2);
grid[0][b] = val(visible[0][2], b-2);
grid[1][b] = val(visible[1][2], b-2);
grid[2][b] = val(visible[1][2], 50+b-2);
}
// for (int a = 0; a < m; a++) {
// for (int b = 0; b < m; b++) {
// // cerr << grid[a][b] << ' ';
// }
// // cerr << '\n';
// }
// extract current answer from visible[2][2]
int ans = 0;
vector<int> uf(m*m);
iota(uf.begin(), uf.end(), 0);
if (m > 3) {
for (int a = 0; a < 10; a++) {
ans += (val(visible[2][2], 100-a-1)<<a);
}
for (int b = 0; b < m-2; b++) {
for (int a = 0; a < 2; a++) {
grid[b+2][1+a] = val(visible[2][1], 50*a+b);
grid[1+a][b+2] = val(visible[1][2], 50*a+b);
}
grid[b+2][0] = val(visible[2][0], b);
grid[0][b+2] = val(visible[0][2], b);
}
vector<int> starts;
int p = 0;
for (int a = m-1; a >= 2; a--) {
for (int b = 2; b < m; b++) {
if (a != 2 && b != 2) continue;
if (!grid[a][b]) continue;
bool is_start = val(visible[2][2], p+1);
bool is_end = val(visible[2][2], p+45);
int cur = m*a+b;
p++;
if (is_end) {
assert(starts.size());
merge(starts.back(), cur, uf);
starts.pop_back();
// cerr << "0\n";
}
if (is_start) {
starts.push_back(cur);
// cerr << "1\n";
}
}
}
// cerr << visible[2][2] << '\n';
assert(starts.empty());
for (int a = m-1; a >= 2; a--) {
for (int b = 2; b < m; b++) {
if (a != 2 && b != 2) continue;
if (!grid[a][b]) continue;
int cur = m*a+b;
ans -= (uf[cur] == cur); // this cc is currently represented
}
}
}
for (int a = 0; a < m; a++) {
for (int b = 0; b < m; b++) {
if (a < m-1 && grid[a][b] && grid[a+1][b]) merge(m*a+b, m*a+b+m, uf);
if (b < m-1 && grid[a][b] && grid[a][b+1]) merge(m*a+b, m*a+b+1, uf);
}
}
for (int a = 0; a < m; a++) {
for (int b = 0; b < m; b++) {
ans += (grid[a][b] && uf[m*a+b] == m*a+b);
}
}
string res(100, '0');
res[0] = visible[0][0][0];
if (i == 0) {
int p = 0;
while (ans) {
res[p] = '0'+(ans&1);
ans /= 2;
p++;
}
}
else {
for (int p = 0; p < 10; p++, ans /= 2) res[100-p-1] = '0'+(ans&1);
vector<char> seen(m*m, 0);
int p = 0;
for (int a = m-1; a >= 0; a--) {
for (int b = 0; b < m; b++) {
if (a && b) continue;
if (!grid[a][b]) continue;
res[45+p] = '0'+seen[find(m*a+b, uf)];
seen[find(m*a+b, uf)] = 1;
p++;
}
}
p = 0;
fill(seen.begin(), seen.end(), 0);
for (int b = m-1; b >= 0; b--) {
for (int a = 0; a < m; a++) {
if (a && b) continue;
res[1+p] = '0'+seen[find(m*a+b, uf)];
seen[find(m*a+b, uf)] = 1;
p++;
}
}
}
for (int a = 0; a < m; a++) {
delete[] grid[a];
}
delete[] grid;
return res;
}
if (i > j) {
if (i & 1 == 0) return visible[0][0];
string res(100, '0');
for (int a = 0; a < 2; a++) {
for (int b = 0; b < m; b++) {
if (b <= 2) res[50*a+b] = visible[b][a][0];
else res[50*a+b] = visible[2][0][50*a+b-2];
}
}
return res;
}
if (j & 1 == 0) return visible[0][0];
string res(100, '0');
for (int a = 0; a < 2; a++) {
for (int b = 0; b < m; b++) {
if (b <= 2) res[50*a+b] = visible[a][b][0];
else res[50*a+b] = visible[0][2][50*a+b-2];
}
}
return res;
}
Compilation message
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:165:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
165 | if (i & 1 == 0) return visible[0][0];
| ~~^~~~
mars.cpp:175:12: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
175 | if (j & 1 == 0) return visible[0][0];
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
