Submission #726190

#TimeUsernameProblemLanguageResultExecution timeMemory
726190hollwo_pelwMars (APIO22_mars)C++17
0 / 100
1 ms328 KiB
#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) { assert(0); 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); } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...