| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726191 |
2023-04-18T16:30:41 Z |
hollwo_pelw |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
604 KB |
#include "mars.h"
#ifdef hollwo_pelw_local
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
#define pii pair<int, int>
#define x first
#define y second
bool board[N][N];
int vis[N][N];
vector<pii> adj[N][N]; // boundary of 4 corners
const int dx[] = {-1, 0, +1, 0};
const int dy[] = {0, -1, 0, +1};
void dfs(int x, int y) {
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || ny < 0) continue;
if (board[nx][ny] && vis[nx][ny] == -1)
vis[nx][ny] = vis[x][y], dfs(nx, ny);
}
for (auto [nx, ny] : adj[x][y]) {
if (board[nx][ny] && vis[nx][ny] == -1)
vis[nx][ny] = vis[x][y], dfs(nx, ny);
}
}
int decode(const string &s) {
int v = 0, len = s.size();
for (int i = 0; i < min(20, len); i++)
v |= (s[i] == '1') << i;
return v;
}
int decode(const string &s, int p, int len) {
return decode(s.substr(p, len));
}
string encode(int len, int v) {
// cout << "encode " << len << ' ' << v << '\n';
string res(len, '0');
for (int i = 0; i < min(20, len); i++)
res[i] = "01"[v >> i & 1];
// cout << res << '\n';
return res;
}
string process(vector<vector<string>> s, int i, int j, int k, int n) {
memset(vis, -1, sizeof vis);
memset(board, 0, sizeof board);
for (int i = 0; i <= 2 * n; i++) {
for (int j = 0; j <= 2 * n; j++)
adj[i][j].clear();
}
if (n == 1) {
for (int i = 0; i <= 2 * n; i++) {
for (int j = 0; j <= 2 * n; j++) {
board[i][j] = s[i][j][0] == '1';
}
}
int res = 0;
for (int i = 0; i <= 2 * n; i++) for (int j = 0; j <= 2 * n; j++) {
if (board[i][j] && vis[i][j] == -1) {
vis[i][j] = res ++, dfs(i, j);
}
}
return encode(100, res);
}
assert(0);
pii cur[N][N], nxt[N][N];
// cout << "PHRASE " << n << ' ' << k << " -> " << "x = " << i << ' ' << "y = " << j << '\n';
for (int x = 0; x <= 2 * n; x++) {
for (int y = 0; y <= 2 * n; y++) {
cur[x][y] = {min(x * n / 2, x + 2 * k) , min(y * n / 2, y + 2 * k) };
nxt[x][y] = {min(x * n / 2, x + 2 * (k + 1)), min(y * n / 2, y + 2 * (k + 1))};
// cout << x << ' ' << y << " -> " << nxt[x][y].x << ' ' << nxt[x][y].y << '\n';
}
}
vector<pii> bound[4];
for (int i = 0; i <= n; i++) {
bound[0].push_back({n, i});
bound[1].push_back({n, n * 2 - i});
bound[2].push_back({n, i});
bound[3].push_back({n, n * 2 - i});
}
for (int i = 1; i <= n; i++) {
bound[0].push_back({n - i, n});
bound[1].push_back({n - i, n});
bound[2].push_back({n + i, n});
bound[3].push_back({n + i, n});
}
if (k == n - 1) {
// solve last step
int res = 0;
for (int fx : {0, 2}) for (int fy : {0, 2}) {
auto curbound = bound[fx + fy / 2];
string mask = s[fx][fy].substr(0, 41);
string A = s[fx][fy].substr(41, 21);
string B = s[fx][fy].substr(62, 21);
res += decode(s[fx][fy], 83, 17);
// cout << s[fx][fy].substr(83, 17) << '\n';
// cout << res << '\n';
vector<int> comp;
for (int i = 0; i <= 2 * n; i++) {
if (mask[i] & 1) {
auto [x, y] = curbound[i];
board[x][y] = 1;
comp.push_back(i);
}
}
vector<int> stk;
for (int i = 0, m = comp.size(); i < m; i++) {
if (A[i] & 1) {
stk.push_back(i);
} else {
auto [x1, y1] = curbound[stk.back()];
auto [x2, y2] = curbound[i];
adj[x1][y1].push_back({x2, y2});
adj[x2][y2].push_back({x1, y1});
}
if (B[i] & 1) {
stk.pop_back();
}
}
}
for (int i = 0; i <= 2 * n; i++) for (int j = 0; j <= 2 * n; j++) {
if (board[i][j] && vis[i][j] == -1) {
vis[i][j] = ++ res, dfs(i, j);
}
}
return encode(100, res);
}
if (k == n - 2) {
// solve second last
if (i % 2 == 1 || j % 2 == 1)
return string(100, '0');
auto curbound = bound[i + j / 2];
int xl = 0, xr = n, yl = 0, yr = n;
if (i) xl += n, xr += n;
if (j) yl += n, yr += n;
// for (int i = 0; i < 3; i++) {
// for (int j = 0; j < 3; j++)
// cout << s[i][j] << '\n';
// }
for (int x = xl; x <= xr; x++) for (int y = yl; y <= yr; y++) {
bool ok = 0;
for (int fx = 3; fx --; ) for (int fy = 3; fy -- && !ok; ) {
int ox = x - cur[i + fx][j + fy].x;
int oy = y - cur[i + fx][j + fy].y;
if (ox < 0 || oy < 0 || ox >= 10 || oy >= 10)
continue;
// cout << x << ' ' << y << " keep in " << ox << ' ' << oy << '\n';
// cout << "-> " << s[fx][fy][ox * 10 + oy] << '\n';
board[x][y] = s[fx][fy][ox * 10 + oy] == '1', ok = 1;
}
// cout << board[x][y];
// if (y == yr)
// cout << '\n';
}
int cnt_oth = 0, cnt_bnd = 0;
for (auto [x, y] : curbound) {
if (board[x][y] && vis[x][y] == -1) {
vis[x][y] = ++ cnt_bnd, dfs(x, y);
}
}
// for (int x = xl; x <= xr; x++) for (int y = yl; y <= yr; y++) {
// cout << vis[x][y] << "\t\n"[y == yr];
// }
for (int x = xl; x <= xr; x++) for (int y = yl; y <= yr; y++) {
if (board[x][y] && vis[x][y] == -1)
vis[x][y] = ++ cnt_oth, dfs(x, y);
}
// cout << cnt_bnd << '\n';
// cout << cnt_oth << '\n';
assert((int) curbound.size() == 2 * n + 1);
string mask(41, '0'), A(21, '0'), B(21, '0');
vector<pair<int, int>> comp;
for (int i = 0; i <= 2 * n; i++) {
auto [x, y] = curbound[i];
mask[i] = "01"[board[x][y]];
if (board[x][y])
comp.push_back({i, vis[x][y]});
// cout << mask[i];
}
// cout << '\n';
for (int i = 0, m = comp.size(); i < m; i++) {
bool isA = 1, isB = 1;
for (int j = 0; j < i; j++)
isA &= comp[j].second != comp[i].second;
for (int j = i + 1; j < m; j++)
isB &= comp[j].second != comp[i].second;
A[i] = "01"[isA], B[i] = "01"[isB];
}
// mask = component
// A = open bracket
// B = close bracket
return mask + A + B + encode(17, cnt_oth);
}
// solve other case
// cout << cur[2][3].x << ' ' << cur[2][3].y << '\n';
// cout << nxt[2][3].x << ' ' << nxt[2][3].y << '\n';
string res(100, '0');
for (int x = 0; x < 10; x++) for (int y = 0; y < 10; y++) {
bool ok = 0;
for (int fx = 3; fx --; ) for (int fy = 3; fy -- && !ok; ) {
int ox = x + nxt[i][j].x - cur[i + fx][j + fy].x;
int oy = y + nxt[i][j].y - cur[i + fx][j + fy].y;
if (ox < 0 || ox >= 10 || oy < 0 || oy >= 10)
continue;
res[x * 10 + y] = s[fx][fy][ox * 10 + oy], ok = 1;
// cout << "KEEP " << x << ' ' << y << " = " << res[x * 10 + y] << '\n';
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
