Submission #572815

#TimeUsernameProblemLanguageResultExecution timeMemory
572815baluteshihMars (APIO22_mars)C++17
14 / 100
41 ms2716 KiB
#include "mars.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define X first #define Y second #define SZ(a) ((int)a.size()) #define ALL(v) v.begin(), v.end() #define pb push_back char mp[100][100]; pii boss[100][100]; pii mapping[100000]; pii finds(pii a) { if (a == pii(-1, -1)) return pii(-1, -1); if (a == boss[a.X][a.Y]) return a; return boss[a.X][a.Y] = finds(boss[a.X][a.Y]); } int Union(pii a, pii b) { a = finds(a), b = finds(b); if (a == b) return 0; if (a > b) swap(a, b); //cerr << "Union " << a.X << " " << a.Y << " " << b.X << " " << b.Y << "\n"; boss[b.X][b.Y] = a; return 1; } string process(vector<vector<string>> a, int i, int j, int k, int n) { const int ANS = __lg(((2 * n + 1) * (2 * n + 1) + 1) / 2) + 1; const int SZ = 3; auto decode = [&](string s) { int rt = 0; for (int t = 0; t < SZ(s); ++t) if (s[t] == '1') rt |= 1 << t; return rt; }; auto encode = [](int x, int len) { string rt(len, '0'); for (int t = 0; t < len; ++t) if (x >> t & 1) rt[t] = '1', x -= 1 << t; assert(x == 0); return rt; }; int m = 2 * (n - k - 1); int num = 2 * n - (m + 2) + 2 * n - (m + 2); int nxt = 2 * n - (m) + 2 * n - (m); auto place = [&](int p, int q, int tm) { if (q == tm + 2) return 2 * n - p; return 2 * n - (tm + 3) + p - (tm + 2); }; auto coord = [&](int x, int tm) { if (x <= 2 * n - (tm + 3)) return pii(2 * n - x, tm + 2); x -= 2 * n - (tm + 3); return pii(tm + 2, x + tm + 2); }; auto check = [&](int x, int y) { if (x < m || x >= 2 * n + 1) return 0; if (y < m || y >= 2 * n + 1) return 0; if (x > m + 2 && y > m + 2) return 0; if (boss[x][y].X == -1) return 0; return 1; }; if (i == m && j == m) { if (k == 0 && a[2][2][0] == '1') { a[2][2][100 - ANS] = '1'; a[2][2][1] = '1'; } int sum = decode(a[2][2].substr(100 - ANS, ANS)); //cerr << "prv sum = " << sum << "\n"; for (int p = m; p < m + 3; ++p) for (int q = m; q < m + 3; ++q) { mp[p][q] = a[p - m][q - m][0]; boss[p][q] = pii(p, q); if (mp[p][q] == '1') sum += (p != m + 2 || q != m + 2); else boss[p][q] = pii(-1, -1); } for (int p = m; p < m + 2; ++p) for (int q = m + 3; q < 2 * n + 1; ++q) { mp[p][q] = a[p - m][2][q - m - 2]; mp[q][p] = a[2][p - m][q - m - 2]; boss[p][q] = pii(p, q); if (mp[p][q] == '1') ++sum; else boss[p][q] = pii(-1, -1); boss[q][p] = pii(q, p); if (mp[q][p] == '1') ++sum; else boss[q][p] = pii(-1, -1); } //cerr << "sum = " << sum << "\n"; for (int p = 0; p < num; ++p) mapping[p] = pii(2 * n + 1, 2 * n + 1); mapping[0] = pii(-1, -1); for (int p = 0, nw = 1; p < num; ++p, nw += SZ) { int d = decode(a[2][2].substr(nw, SZ)); pii c = coord(p, m); mapping[d] = min(mapping[d], c); } for (int p = 0, nw = 1; p < num; ++p, nw += SZ) { int d = decode(a[2][2].substr(nw, SZ)); pii c = coord(p, m); //cerr << c.X << " " << c.Y << " code = " << d << ", mapping = " << mapping[d].X << " " << mapping[d].Y << "\n"; boss[c.X][c.Y] = mapping[d]; } /*for (int p = m; p < 2 * n + 1; ++p) for (int q = m; q < 2 * n + 1; ++q) if (check(p, q)) { cerr << "boss " << p << " " << q << " = " << boss[p][q].X << " " << boss[p][q].Y << "\n"; }*/ if (check(m + 2, m + 2)) { if (check(m + 3, m + 2)) Union(pii(m + 2, m + 2), pii(m + 3, m + 2)); if (check(m + 2, m + 3)) Union(pii(m + 2, m + 2), pii(m + 2, m + 3)); } for (int p = m; p < 2 * n + 1; ++p) for (int q = m; q < 2 * n + 1; ++q) if (check(p, q)) { if (check(p + 1, q)) sum -= Union(pii(p, q), pii(p + 1, q)); if (check(p, q + 1)) sum -= Union(pii(p, q), pii(p, q + 1)); } if (k == n - 1) return encode(sum, ANS) + string(100 - ANS, '0'); string rt(1, a[0][0][0]); vector<pii> ele(1, pii(-1, -1)); for (int p = 0; p < nxt; ++p) { pii c = coord(p, m - 2); ele.pb(finds(c)); } sort(ALL(ele)), ele.resize(unique(ALL(ele)) - ele.begin()); for (int p = 0; p < nxt; ++p) { pii c = coord(p, m - 2); rt += encode(lower_bound(ALL(ele), finds(c)) - ele.begin(), SZ); } rt.resize(100 - ANS, '0'); return rt + encode(sum, ANS); } if (i == m) { a[2][0].pop_back(), a[2][0].pop_back(); a[2][0].insert(a[2][0].begin(), a[1][0][0]); a[2][0].insert(a[2][0].begin(), a[0][0][0]); return a[2][0]; } if (j == m) { a[0][2].pop_back(), a[0][2].pop_back(); a[0][2].insert(a[0][2].begin(), a[0][1][0]); a[0][2].insert(a[0][2].begin(), a[0][0][0]); return a[0][2]; } return a[0][0]; }

Compilation message (stderr)

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:59:10: warning: variable 'place' set but not used [-Wunused-but-set-variable]
   59 |     auto place = [&](int p, int q, int tm) {
      |          ^~~~~
#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...