| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 588491 |
2022-07-03T11:27:46 Z |
Joshc |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
300 KB |
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define f first
#define s second
const int OFFSET = 1e6;
/*
00 = nothing
01 = left bracket
10 = rightbracket
11 = underscore
*/
string tobracket(int n, vector<vector<int>> comp) {
// Given a list of components, generate the bracket sequence
string res(100, '0');
for (vector<int>& v : comp) {
if (v.size() == 1) continue;
res[2*v[0]+1] = '1';
res[2*v.back()] = '1';
for (int i=1; i+1<v.back(); i++) res[2*i] = res[2*i+1] = '1';
}
return res;
}
vector<vector<int>> tocomp(int n, string s) {
// Given a bracket sequence, return the list of components
vector<vector<int>> res, stack;
for (int i=0; i<n; i++) {
if (s[i*2] == '0' && s[i*2+1] == '0') res.push_back({i});
else if (s[i*2] == '0' && s[i*2+1] == '1') stack.push_back({i});
else if (s[i*2] == '1' && s[i*2+1] == '0') {
stack.back().push_back(i);
res.push_back(stack.back());
stack.pop_back();
} else stack.back().push_back(i);
}
return res;
}
vector<int> getblocks(string frontier) {
// split the current frontier into blocks
vector<int> res(frontier.size(), -1);
int cur = -1;
for (int i=0; i<frontier.size(); i++) {
if (frontier[i] == '1') {
if (!i || frontier[i-1] == '0') cur++;
res[i] = cur;
}
}
return res;
}
struct dsu {
unordered_map<int, int> parent, sz;
int comps = 0;
int root(int x) {
if (parent.find(x) == parent.end()) {
sz[x] = 1;
comps++;
return parent[x] = x;
}
return x == parent[x] ? x : parent[x] = root(parent[x]);
}
void join(int x, int y) {
x = root(x);
y = root(y);
if (x == y) return;
comps--;
if (sz[x] > sz[y]) swap(x, y);
parent[x] = y;
sz[y] += sz[x];
}
vector<vector<int>> getcomps() {
vector<vector<int>> res;
unordered_map<int, vector<int>> x;
for (pii p : parent) x[root(p.f)].push_back(p.f);
for (auto p : x) res.push_back(p.s);
return res;
}
};
vector<int> reduce(vector<int> v) {
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end())-v.begin());
return v;
}
string process(vector<vector<string>> a, int i, int j, int k, int n) {
//printf("Process %d %d %d\n", i, j, k);
string res(100, '0');
if (i%2 == 0 && i && i >= j+1) {
if (k == 0) {
res[0] = a[0][0][0];
res[1] = a[0][1][0];
res[2] = a[1][0][0];
res[3] = a[1][1][0];
res[4] = a[2][0][0];
res[5] = a[2][1][0];
} else {
for (int i=0; i<96; i++) res[i+4] = a[2][0][i];
res[0] = a[0][0][0];
res[1] = a[0][1][0];
res[2] = a[1][0][0];
res[3] = a[1][1][0];
}
return res;
}
if (j%2 == 0 && j && j >= i+1) {
if (k == 0) {
res[0] = a[0][0][0];
res[1] = a[1][0][0];
res[2] = a[0][1][0];
res[3] = a[1][1][0];
res[4] = a[0][2][0];
res[5] = a[1][2][0];
} else {
for (int i=0; i<96; i++) res[i+4] = a[0][2][i];
res[0] = a[0][0][0];
res[1] = a[1][0][0];
res[2] = a[0][1][0];
res[3] = a[1][1][0];
}
}
if (i == 2*(n-k-1) && i == j) {
if (k == 0) {
string frontier;
frontier += a[2][0][0];
frontier += a[1][0][0];
frontier += a[0][0][0];
frontier += a[0][1][0];
frontier += a[0][2][0];
vector<int> blocks = getblocks(frontier);
int x = *max_element(blocks.begin(), blocks.end())+1;
/*printf("Blocks: ");
for (int i : blocks) printf("%d ", i);
printf("\n");*/
unordered_map<int, int> pos = {{6, 0}, {3, 1}, {0, 2}, {1, 3}, {2, 4}};
dsu d;
for (int i=0; i<3; i++) {
for (int j=0; j<3; j++) {
if (a[i][j][0] == '1') d.root(i*3+j); // make sure node is considered
if (i != 2 && a[i][j][0] == '1' && a[i+1][j][0] == '1') d.join(i*3+j, (i+1)*3+j);
if (j != 2 && a[i][j][0] == '1' && a[i][j+1][0] == '1') d.join(i*3+j, i*3+j+1);
}
}
vector<vector<int>> comps;
for (vector<int>& comp : d.getcomps()) {
vector<int> cur;
//printf("Comp: ");
for (int i : comp) {
//printf("%d ", i);
if (pos.find(i) != pos.end()) cur.push_back(blocks[pos[i]]);
}
//printf("\n");
if (cur.empty()) continue;
comps.push_back(reduce(cur));
}
/*for (auto i : comps) {
for (int j : i) printf("%d ", j);
printf("\n");
}*/
if (n == 1) {
for (int i=0; i<10; i++) {
if (d.comps&(1<<i)) res[i] = '1';
}
return res;
}
res = tobracket(x, comps);
for (int i=0; i<10; i++) {
if (d.comps&(1<<i)) res[i+90] = '1';
}
return res;
}
// for convenience, let's just fill in the entire bottom right square
int sz = 2*n+1-i;
vector<string> grid(sz, string(sz, '0'));
grid[0][0] = a[0][0][0];
grid[0][1] = a[0][1][0];
grid[1][0] = a[1][0][0];
grid[1][1] = a[1][1][0];
for (int i=0; i<sz-2; i++) {
grid[i+2][0] = a[2][0][i*2];
grid[i+2][1] = a[2][0][i*2+1];
grid[i+2][2] = a[2][1][i*2+1];
grid[0][i+2] = a[0][2][i*2];
grid[1][i+2] = a[0][2][i*2+1];
grid[2][i+2] = a[1][2][i*2+1];
}
dsu d;
vector<int> order;
for (int i=2; i<sz; i++) {
if (grid[i][2] == '1') d.root(i*100+2);
if (grid[2][i] == '1') d.root(200+i);
}
string inner; // store the inner frontier
for (int i=sz-1; i>1; i--) {
inner += grid[i][2];
order.push_back(i*100+2);
}
for (int i=3; i<sz; i++) {
inner += grid[2][i];
order.push_back(200+i);
}
vector<int> innerblocks = getblocks(inner);
unordered_map<int, int> m;
for (int i=0; i<innerblocks.size(); i++) m[innerblocks[i]] = order[i];
int x = *max_element(innerblocks.begin(), innerblocks.end())+1;
vector<vector<int>> innercomps = tocomp(x, a[2][2]);
for (vector<int>& comp : innercomps) {
for (int i : comp) d.join(m[comp[0]], m[i]);
}
d.comps = 0;
for (int i=0; i<10; i++) {
if (a[2][2][90+i] == '1') d.comps |= 1<<i;
}
for (int i=0; i<sz; i++) {
for (int j=0; j<sz; j++) {
if (grid[i][j] == '1') d.root(i*100+j);
}
}
for (int i=0; i<sz; i++) {
for (int j=0; j<sz; j++) {
if (i+1 != sz && grid[i][j] == '1' && grid[i+1][j] == '1') d.join(i*100+j, (i+1)*100+j);
if (j+1 != sz && grid[i][j] == '1' && grid[i][j+1] == '1') d.join(i*100+j, i*100+j+1);
}
}
order.clear();
string outer;
unordered_map<int, int> pos;
for (int i=sz-1; i>=0; i--) {
pos[i*100] = outer.size();
outer += grid[i][0];
}
for (int i=1; i<sz; i++) {
pos[i] = outer.size();
outer += grid[0][i];
}
vector<int> blocks = getblocks(outer);
vector<vector<int>> comps;
for (vector<int>& comp : d.getcomps()) {
vector<int> cur;
for (int i : comp) {
if (pos.find(i) != pos.end()) cur.push_back(blocks[pos[i]]);
}
if (cur.empty()) continue;
comps.push_back(reduce(cur));
}
if (k == n-1) {
for (int i=0; i<10; i++) {
if (d.comps&(1<<i)) res[i] = '1';
}
return res;
}
res = tobracket(x, comps);
for (int i=0; i<10; i++) {
if (d.comps&(1<<i)) res[i+90] = '1';
}
return res;
}
return a[0][0];
}
Compilation message
mars.cpp: In function 'std::vector<int> getblocks(std::string)':
mars.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i=0; i<frontier.size(); i++) {
| ~^~~~~~~~~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:228:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | for (int i=0; i<innerblocks.size(); i++) m[innerblocks[i]] = order[i];
| ~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
