| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 595393 |
2022-07-13T17:07:46 Z |
lunchbox |
Mars (APIO22_mars) |
C++17 |
|
8 ms |
2096 KB |
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> ds;
dsu(int n) {
ds.assign(n, -1);
}
const int& operator[](int i) {
return ds[i];
}
int find(int i) {
return ds[i] < 0 ? i : ds[i] = find(ds[i]);
}
int size(int i) {
return -ds[find(i)];
}
bool same(int i, int j) {
return find(i) == find(j);
}
bool join(int i, int j) {
i = find(i), j = find(j);
if (i == j)
return false;
if (ds[i] > ds[j])
swap(i, j);
ds[i] += ds[j], ds[j] = i;
return true;
}
};
string fill(string s) {
while (s.size() < 100)
s += "0";
return s;
}
string process(vector<vector<string>> ss, int i, int j, int k, int n) {
int b = 2 * (n - k - 1), n_ = (k + 1) * 2 + 1;
if (i < b && j < b)
return ss[0][0];
else if (i == b && j != b) {
swap(ss[0][1], ss[1][0]);
swap(ss[0][2], ss[2][0]);
swap(ss[1][2], ss[2][1]);
string s;
for (int i1 = 0; i1 < 2; i1++) {
for (int j1 = 0; j1 < 2; j1++)
s += ss[i1][j1][0];
for (int j1 = 0; j1 < n_ - 2; j1++)
s += ss[i1][2][j1];
}
return fill(s);
} else if (i != b && j == b) {
string s;
for (int i1 = 0; i1 < 2; i1++) {
for (int j1 = 0; j1 < 2; j1++)
s += ss[i1][j1][0];
for (int j1 = 0; j1 < n_ - 2; j1++)
s += ss[i1][2][j1];
}
return fill(s);
} else {
if (k == 0) {
dsu ds(n_ * n_);
for (int i1 = 0; i1 < n_; i1++)
for (int j1 = 0; j1 < n_; j1++)
if (ss[i1][j1][0] == '1') {
if (i1 > 0 && ss[i1 - 1][j1][0] == '1')
ds.join(i1 * n_ + j1, (i1 - 1) * n_ + j1);
if (j1 > 0 && ss[i1][j1 - 1][0] == '1')
ds.join(i1 * n_ + j1, i1 * n_ + (j1 - 1));
}
int c = 0;
for (int i1 = 0; i1 < n_; i1++)
for (int j1 = 0; j1 < n_; j1++)
if (ss[i1][j1][0] == '1' && ds[i1 * n_ + j1] < 0)
c++;
if (n == 1) {
string s(100, '0');
for (int x = 0; x < 10; x++)
s[x] = '0' + (c >> x & 1);
return s;
}
vector<int> ii;
for (int i1 = 3 - 1; i1 >= 0; i1--)
if (ss[0][i1][0] == '1' && (i1 == 2 || ss[0][i1 + 1][0] == '0'))
ii.push_back(ds.find(0 * n_ + i1));
for (int i1 = 1; i1 < 3; i1++)
if (ss[i1][0][0] == '1' && ss[i1 - 1][0][0] == '0')
ii.push_back(ds.find(i1 * n_ + 0));
vector<int> stack, marked(n_ * n_);
string s(100, '0');
for (int i1 = 0; i1 < (int) ii.size(); i1++)
if (!stack.empty() && marked[ii[i1]]) {
while (ii[stack.back()] != ii[i1]) {
s[stack.back() << 1 | 1] = '1';
stack.pop_back();
}
stack.pop_back();
stack.push_back(i1);
} else {
s[i1 << 1 | 0] = '1';
marked[ii[i1]] = 1, stack.push_back(i1);
}
while (!stack.empty()) {
s[stack.back() << 1 | 1] = '1';
stack.pop_back();
}
for (int x = 0; x < 10; x++)
s[90 + x] = '0' + (c >> x & 1);
return s;
} else {
vector<vector<int>> gr(n_, vector<int>(n_, 0));
for (int i1 = 0; i1 < 2; i1++)
for (int j1 = 0; j1 < 2; j1++)
gr[i1][j1] = ss[i1][j1][0] - '0';
for (int i1 = 0; i1 < n_ - 2; i1++)
for (int j1 = 0; j1 < 2; j1++) {
gr[j1][i1 + 2] = ss[0][2][j1 * (n_ - 2) + i1] - '0';
gr[i1 + 2][j1] = ss[2][0][j1 * (n_ - 2) + i1] - '0';
}
for (int i1 = 0; i1 < n_ - 2; i1++) {
gr[2][i1 + 2] = ss[1][2][n_ - 2 + i1] - '0';
gr[i1 + 2][2] = ss[2][1][n_ - 2 + i1] - '0';
}
int c = 0;
for (int x = 0; x < 10; x++)
if (ss[2][2][90 + x] == '1')
c |= 1 << x;
for (int i1 = 0; i1 < n_; i1++)
for (int j1 = 0; j1 < 2; j1++)
c += gr[i1][j1] + gr[j1][i1];
c -= gr[0][0];
c -= gr[0][1];
c -= gr[1][0];
c -= gr[1][1];
dsu ds(n_ * n_);
for (int i1 = 0; i1 < n_; i1++) {
if (gr[0][i1] && gr[1][i1] && ds.join(0 * n_ + i1, 1 * n_ + i1))
c--;
if (gr[i1][0] && gr[i1][1] && ds.join(i1 * n_ + 0, i1 * n_ + 1))
c--;
for (int j1 = 0; j1 < 2; j1++) {
if (i1 < n_ - 1 && gr[i1][j1] && gr[i1 + 1][j1] && ds.join(i1 * n_ + j1, (i1 + 1) * n_ + j1))
c--;
if (i1 < n_ - 1 && gr[j1][i1] && gr[j1][i1 + 1] && ds.join(j1 * n_ + i1, j1 * n_ + (i1 + 1)))
c--;
}
}
for (int i1 = n_ - 2; i1 >= 2; i1--)
if (gr[2][i1] && gr[2][i1 + 1])
ds.join(2 * n_ + i1, 2 * n_ + (i1 + 1));
for (int i1 = 3; i1 < n_; i1++)
if (gr[i1][2] && gr[i1 - 1][2])
ds.join(i1 * n_ + 2, (i1 - 1) * n_ + 2);
vector<int> ii;
for (int i1 = n_ - 1; i1 >= 2; i1--)
if (gr[2][i1] && (i1 == n_ - 1 || !gr[2][i1 + 1]))
ii.push_back(ds.find(2 * n_ + i1));
for (int i1 = 3; i1 < n_; i1++)
if (gr[i1][2] && !gr[i1 - 1][2])
ii.push_back(ds.find(i1 * n_ + 2));
vector<int> stack, mark(ii.size());
for (int i1 = 0; i1 < (int) ii.size(); i1++) {
if (ss[2][2][i1 << 1 | 0] == '1')
stack.push_back(i1);
mark[i] = stack.back();
for (int j1 = 0; j1 < i1; j1++)
if (mark[j1] == mark[i1])
ds.join(ii[i1], ii[j1]);
if (ss[2][2][i1 << 1 | 1] == '1')
stack.pop_back();
}
for (int i1 = 2; i1 < n_; i1++) {
if (gr[1][i1] && gr[2][i1] && ds.join(1 * n_ + i1, 2 * n_ + i1))
c--;
if (gr[i1][1] && gr[i1][2] && ds.join(i1 * n_ + 1, i1 * n_ + 2))
c--;
}
ii.clear();
for (int i1 = n_ - 1; i1 >= 0; i1--)
if (gr[0][i1] && (i1 == n - 1 || !gr[0][i1 + 1]))
ii.push_back(ds.find(0 * n_ + i1));
for (int i1 = 1; i1 < n_; i1++)
if (gr[i1][0] && !gr[i1 - 1][0])
ii.push_back(ds.find((i1 - 1) * n_ + 0));
vector<int> marked(n_ * n_);
string s(100, '0');
if (k == n - 1) {
for (int x = 0; x < 10; x++)
s[x] = '0' + (c >> x & 1);
return s;
}
for (int i1 = 0; i1 < (int) ii.size(); i1++)
if (!stack.empty() && marked[ii[i1]]) {
while (ii[stack.back()] != ii[i1]) {
s[stack.back() << 1 | 1] = '1';
stack.pop_back();
}
stack.pop_back();
stack.push_back(i1);
} else {
s[i1 << 1 | 0] = '1';
marked[ii[i1]] = 1, stack.push_back(i1);
}
while (!stack.empty()) {
s[stack.back() << 1 | 1] = '1';
stack.pop_back();
}
for (int x = 0; x < 10; x++)
s[90 + x] = '0' + (c >> x & 1);
return s;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2096 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
200 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
