| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 739185 |
2023-05-10T06:54:59 Z |
PixelCat |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
220 KB |
#include "mars.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;
struct DSU {
int p[400];
void init() {
memset(p, 0, sizeof(p));
}
int find(int n) {
if(!p[n]) return n;
return p[n] = find(p[n]);
}
void uni(int a, int b) {
// cerr << "link " << a << ", " << b << "\n";
a = find(a); b = find(b);
if(a == b) return;
p[a] = b;
}
bool same(int a, int b) {
return find(a) == find(b);
}
} dsu;
// {cnt, max id}
pii decode(int len, const string &s, vector<int> &res, int k) {
if(k == 0) {
res.clear();
res.eb(s[0] - '0');
return pii(0, res[0]);
}
int cnt = 0;
For(i, 0, 6) cnt += (s[i] - '0') << i;
int last = 0;
res.clear();
int i = 7;
int mx = 0;
while(len--) {
int b = s[i] - '0'; i++;
if(!b) {
res.eb(0);
} else if(!last) {
last = 0;
For(j, 0, 3) {
last += (s[i] - '0') << j;
i++;
}
res.eb(last);
mx = max(mx, last);
} else {
res.eb(last);
}
last = b;
}
return pii(cnt, mx);
}
string process(vector<vector<string>> a, int I, int J, int k, int n) {
// cerr << I << "," << J << " " << k << " " << n << "\n" << flush;
#define ID(x, y) ((x) * side_len + (y))
#define empty(id) dsu.same(id, cell_count)
dsu.init();
int side_len = k * 2 + 3;
int cell_count = side_len * side_len;
pii res[3][3];
int cur_id = cell_count;
For(i, 0, 2) For(j, 0, 2) {
int len = side_len - 2;
vector<int> v;
auto p = decode(2 * len - 1, a[i][j], v, k);
res[i][j] = p;
int x = len - 1 + i, y = j;
For(i2, 0, len - 1) {
if(v[i2] == 0) {
dsu.uni(ID(x, y), cell_count);
} else {
dsu.uni(ID(x, y), cur_id + v[i2]);
}
y++;
}
y--; x--;
For(i2, len, sz(v) - 1) {
if(v[i2] == 0) {
dsu.uni(ID(x, y), cell_count);
} else {
dsu.uni(ID(x, y), cur_id + v[i2]);
}
x--;
}
cur_id += p.S;
// string oao = "";
// for(auto &i2:v) {
// if(i2) oao.push_back('1');
// else oao.push_back('0');
// }
// cerr << oao << "\n";
// cerr << ": ";
// for(auto &i2:v) cerr << i2 << " ";
// cerr << "\n";
}
For(i, 0, side_len - 1) For(j, 0, side_len - 2) if(i >= k * 2 || j >= k * 2) {
if(!empty(ID(i, j)) && !empty(ID(i, j + 1))) {
dsu.uni(ID(i, j), ID(i, j + 1));
}
if(!empty(ID(j, i)) && !empty(ID(j + 1, i))) {
dsu.uni(ID(j, i), ID(j + 1, i));
}
}
// For(i, 0, side_len - 1) {
// For(j, 0, side_len - 1) {
// cerr << empty(ID(i, j));
// }
// cerr << "\n";
// }
map<int, int> used_cc;
int cc_count = 0;
string bor;
int last = 0;
For(y, 0, side_len - 1) {
int x = side_len - 1;
int cell_id = ID(x, y);
if(empty(cell_id)) {
bor.push_back('0');
last = 0;
} else if(last != 0) {
bor.push_back('1');
last = 1;
} else {
bor.push_back('1');
int rt = dsu.find(cell_id);
if(!used_cc.count(rt)) {
cc_count++;
used_cc[rt] = cc_count;
}
int z = used_cc[rt];
For(i, 0, 3) bor.push_back((char)('0' + ((z & (1 << i)) != 0)));
last = 1;
}
// cerr << last;
}
Forr(x, side_len - 2, 0) {
int y = side_len - 1;
int cell_id = ID(x, y);
if(empty(cell_id)) {
bor.push_back('0');
last = 0;
} else if(last != 0) {
bor.push_back('1');
last = 1;
} else {
bor.push_back('1');
int rt = dsu.find(cell_id);
if(!used_cc.count(rt)) {
cc_count++;
used_cc[rt] = cc_count;
}
int z = used_cc[rt];
For(i, 0, 3) bor.push_back((char)('0' + ((z & (1 << i)) != 0)));
last = 1;
}
// cerr << last;
}
// cerr << "\n";
// For(i, 0, side_len - 1) {
// For(j, 0, side_len - 1) {
// if(empty(ID(i, j)) || (i < k * 2 && j < k * 2)) cerr << "0 ";
// else cerr << dsu.find(ID(i, j)) << " ";
// // cerr << empty(ID(i, j));
// }
// cerr << "\n";
// }
int cnt = res[0][0].F;
// cerr << cnt << " !!!\n";
if(k == n - 1) cnt += sz(used_cc);
For(i, 0, side_len - 2) For(j, 0, side_len - 2) if(i >= k * 2 || j >= k * 2) {
int rt = dsu.find(ID(i, j));
if(!empty(ID(i, j)) && !used_cc.count(rt)) {
// cerr << rt << "?\n";
used_cc[rt] = 0;
cnt++;
}
}
string cnt_s = "0000000";
For(i, 0, 6) if(cnt & (1 << i)) cnt_s[i] = '1';
string ret = cnt_s;
if(k != n - 1) ret = ret + bor;
// cerr << cnt << " " << bor << "\n" << flush;
while(sz(ret) < 100) ret.push_back('0');
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
