| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 578507 |
2022-06-17T07:30:10 Z |
8e7 |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
312 KB |
//Challenge: Accepted
//#define _GLIBCXX_DEBUG 1
#include <bits/stdc++.h>
#include "mars.h"
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 105
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1<<30;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool vis[3 * maxn];
int color[3 * maxn];
vector<int> adj[3 * maxn];
void dfs(int n, int c) {
vis[n] = 1;
color[n] = c;
for (int v:adj[n]) {
if (!vis[v]) dfs(v, c);
}
}
std::string process(std::vector <std::vector<std::string>> a, int X, int Y, int k, int n) {
int len = 2 * n + 1, m = len - 2 * k - 3;
string ret = a[0][0];
auto propagate = [&] (bool type) {
if (type) {
ret[1] = a[1][0][0];
for (int i = 2;i < 100;i++) ret[i] = a[2][0][i-2];
} else {
ret[1] = a[0][1][0];
for (int i = 2;i < 100;i++) ret[i] = a[0][2][i-2];
}
};
if (X < m-1 && Y < m-1) {
return ret;
} else if (X < m && Y < m) {
if (X == m - 1 && Y == m - 1) {
int l = 1 + 2 * k;
string s;
for (int i = 0;i < l;i++) s += a[2][1][i];
reverse(s.begin(), s.end());
s += a[1][1][0];
for (int i = 0;i < l;i++) s += a[1][2][i];
for (int i = 0;i < s.size();i++) ret[i] = s[i];
ret[99] = a[0][0][0];
} else {
propagate(X == m-1);
}
} else if (X == m && Y == m) {
for (int i = 0;i < 3 * maxn;i++) adj[i].clear(), vis[i] = 0;
int l = 1 + 2 * k;
int cnt = 0; //the number of lone islands
for (int i = 83;i < 98;i++) cnt += (1<<(i-83)) * (a[2][2][i] - '0');
string s, t, mid; // s is current row, t is row for previous iter
if (k == 0) {
s = a[2][0][0]; s += a[1][0][0];s += a[0][0][0];s += a[0][1][0];s += a[0][2][0];
mid = a[2][1][0]; mid += a[1][1][0];mid += a[1][2][0];
t = a[2][2][0];
} else {
for (int i = 0;i < l;i++) s += a[2][0][i];
reverse(s.begin(), s.end());
s += a[1][0][0];
s += a[0][0][0];
s += a[0][1][0];
for (int i = 0;i < l;i++) s += a[0][2][i];
for (int i = 0;i < l;i++) mid += a[2][1][i];
reverse(mid.begin(), mid.end());
mid += a[1][1][99];
for (int i = 0;i < l;i++) mid += a[1][2][i];
t += a[2][2][98];
for (int i = 0;i < 2 * (l - 2) + 1;i++) t += a[1][1][i];
t += a[2][2][99];
}
debug(k);
debug(s);
debug(mid);
debug(t);
ret[98] = s[0];
ret[99] = s.back();
//parse component info for t
vector<int> comp(maxn, 0), last(maxn, 0);
vector<int> seg;
if (k > 0) {
int cur = 0, prv = 0;
for (char i:t) {
if (i == '1' && prv == 0) cur++;
if (i == '1') seg.push_back(cur);
else seg.push_back(0);
prv = i - '0';
}
//cur is number of components
stack<int> stk;
for (int i = 0;i < 2 * cur;i += 2) {
int type = (a[2][2][i] - '0') + (a[2][2][i+1] - '0') * 2;
if (type == 0) comp[i/2+1] = i/2+1;
else if (type == 1) {
comp[i/2+1] = i/2+1;
stk.push(i/2+1);
} else if (type == 2) {
comp[i/2+1] = stk.top();
stk.pop();
} else {
comp[i/2+1] = stk.top();
}
}
}
//build graph
auto addedge = [&] (int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
};
auto check = [&] (int u, int v, char c, char d) {
if (c == '1' && d == '1') addedge(u, v);
};
if (k > 0) {
for (int i = 0;i < t.size();i++) {
if (t[i] == '1') {
seg[i] = comp[seg[i]];
if (last[seg[i]]) {
addedge(i, last[seg[i]]);
}
last[seg[i]] = i;
}
}
}
for (int i = 0;i < l;i++) check(i, maxn+i, t[i], mid[i]);
for (int i = 0;i <= l;i++) check(maxn+i, 2*maxn+i, mid[i], s[i]);
for (int i = l;i < 2*l - 1;i++) check(i, maxn+i+1, t[i], mid[i+1]);
for (int i = l+1;i < 2*l + 1;i++) check(maxn+i, 2*maxn+i+1, mid[i], s[i+1]);
for (int i = 1;i < 2 * l+3;i++) {
if (i < 2*l - 1) check(i-1, i, t[i-1], t[i]);
if (i < 2*l + 1) check(maxn + i-1, maxn + i, mid[i-1], mid[i]);
check(2*maxn + i-1, 2*maxn + i, s[i-1], s[i]);
}
int upper = 0;
{
int cur = 0;
for (int i = 0;i < 2 * l + 3;i++) {
if (s[i] == '1' && !vis[2*maxn + i]) {
cur++;
debug("dfs s", i);
dfs(2*maxn + i, cur);
}
}
upper = cur;
}
for (int i = 0;i < 2 * l + 1;i++) {
if (mid[i] == '1' && !vis[maxn + i]) {
cnt++;
debug("dfs mid", i);
dfs(maxn + i, 0);
}
}
for (int i = 0;i < 2 * l - 1;i++) {
if (t[i] == '1' && !vis[i]) {
cnt++;
debug("dfs t", i);
dfs(i, 0);
}
}
if (k == n-1) {
upper += cnt;
for (int i = 0;i < 100;i++) ret[i] = '0';
for (int i = 0;i < 100;i++) ret[i] = '0';
for (int i = 0;i < 20;i++) {
ret[i] = ((upper>>i) & 1) + '0';
}
return ret;
}
//encodes component info
{
stack<int> stk;
int prv = 0;
vector<pii> vec;
vector<int> st(maxn, inf), en(maxn, -1);
for (int i = 0;i < 2 * l+3;i += 2) {
if (s[i] == '1' && prv == 0) {
int c = color[2*maxn+i];
vec.push_back({c, i});
st[c] = min(st[c], i);
en[c] = max(en[c], i);
}
prv = i - '0';
}
int idx = 0;
for (auto [c, i]:vec) {
if (i == st[c] && i == en[c]) {
ret[idx] = '0', ret[idx+1] = '0';
} else if (i == st[c]) {
ret[idx] = '1', ret[idx+1] = '0';
} else if (i == en[c]) {
ret[idx] = '0', ret[idx+1] = '1';
} else {
ret[idx] = '1', ret[idx+1] = '1';
}
idx += 2;
}
}
//encodes cnt
for (int i = 83;i < 98;i++) {
ret[i] = ((cnt>>(i-83)) & 1) + '0';
}
debug(k, ret);
} else {
propagate(X == m);
}
return ret;
}
/*
1
3
0 1 1 0 0 1 1
1 0 0 1 0 0 1
1 1 0 0 1 1 0
0 0 0 1 1 1 1
0 0 1 1 0 0 0
0 1 0 0 1 1 1
1 1 1 0 0 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:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i = 0;i < s.size();i++) ret[i] = s[i];
| ~~^~~~~~~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:101:3: note: in expansion of macro 'debug'
101 | debug(k);
| ^~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:102:3: note: in expansion of macro 'debug'
102 | debug(s);
| ^~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:103:3: note: in expansion of macro 'debug'
103 | debug(mid);
| ^~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:104:3: note: in expansion of macro 'debug'
104 | debug(t);
| ^~~~~
mars.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0;i < t.size();i++) {
| ~~^~~~~~~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:173:6: note: in expansion of macro 'debug'
173 | debug("dfs s", i);
| ^~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:183:5: note: in expansion of macro 'debug'
183 | debug("dfs mid", i);
| ^~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:190:5: note: in expansion of macro 'debug'
190 | debug("dfs t", i);
| ^~~~~
mars.cpp:15:20: warning: statement has no effect [-Wunused-value]
15 | #define debug(...) 0
| ^
mars.cpp:238:3: note: in expansion of macro 'debug'
238 | debug(k, ret);
| ^~~~~
| # |
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 |
- |
