| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 572807 |
2022-06-05T10:19:29 Z |
baluteshih |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
312 KB |
#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[2][2][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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
312 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
