-
-
Save wiwiho/e25679f9d059ffd5a933b109cf768ce5 to your computer and use it in GitHub Desktop.
APIO 2022
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "game.h" | |
#include <bits/stdc++.h> | |
#include <bits/extc++.h> | |
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); | |
#define iter(a) a.begin(), a.end() | |
#define riter(a) a.rbegin(), a.rend() | |
#define lsort(a) sort(iter(a)) | |
#define gsort(a) sort(riter(a)) | |
#define pb(a) push_back(a) | |
#define eb(a) emplace_back(a) | |
#define pf(a) push_front(a) | |
#define ef(a) emplace_front(a) | |
#define pob pop_back() | |
#define pof pop_front() | |
#define mp(a, b) make_pair(a, b) | |
#define F first | |
#define S second | |
#define mt make_tuple | |
#define gt(t, i) get<i>(t) | |
#define tomax(a, b) ((a) = max((a), (b))) | |
#define tomin(a, b) ((a) = min((a), (b))) | |
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) | |
#define uni(a) a.resize(unique(iter(a)) - a.begin()) | |
using namespace std; | |
using namespace __gnu_pbds; | |
#define orz | |
#ifdef orz | |
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("[" + string(#a) + "] = ", a) | |
void kout() { cerr << endl; } | |
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); } | |
#define printv(a, b) {bool pvaspace=false; \ | |
for(auto pva : a){ \ | |
if(pvaspace) b << " "; pvaspace=true;\ | |
b << pva;\ | |
}\ | |
b << "\n";} | |
#else | |
#define print(a...) | |
void kout() {} | |
template<class T1, class ... T2> void kout(T1 a, T2 ... e) {} | |
#define printv(a, b) | |
#endif | |
typedef long long ll; | |
typedef unsigned long long ull; | |
typedef long double ld; | |
using pii = pair<int, int>; | |
using pll = pair<ll, ll>; | |
using pdd = pair<ld, ld>; | |
using tiii = tuple<int, int, int>; | |
const ll MOD = 1000000007; | |
const ll MAX = 2147483647; | |
template<typename A, typename B> | |
ostream& operator<<(ostream& o, pair<A, B> p){ | |
return o << '(' << p.F << ',' << p.S << ')'; | |
} | |
ll ifloor(ll a, ll b){ | |
if(b < 0) a *= -1, b *= -1; | |
if(a < 0) return (a - b + 1) / b; | |
else return a / b; | |
} | |
ll iceil(ll a, ll b){ | |
if(b < 0) a *= -1, b *= -1; | |
if(a > 0) return (a + b - 1) / b; | |
else return a / b; | |
} | |
vector<vector<int>> g; | |
vector<vector<bool>> vst; | |
int n; | |
int k; | |
void init(int _n, int _k){ | |
n = _n; | |
k = _k; | |
g.resize(n); | |
vst.resize(k, vector<bool>(n)); | |
for(int i = 0; i < k; i++){ | |
for(int j = i + 1; j < k; j++){ | |
vst[i][j] = true; | |
} | |
} | |
} | |
int add_teleporter(int u, int v){ | |
g[u].eb(v); | |
int ans = 0; | |
for(int i = 0; i < k; i++){ | |
if(!vst[i][u] && i != u) continue; | |
if(vst[i][v]) continue; | |
vst[i][v] = true; | |
queue<int> q; | |
q.push(v); | |
while(!q.empty()){ | |
int now = q.front(); | |
if(now <= i) ans = 1; | |
q.pop(); | |
for(int to : g[now]){ | |
if(vst[i][to]) continue; | |
vst[i][to] = true; | |
q.push(to); | |
} | |
} | |
} | |
return ans; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "mars.h" | |
#include <bits/stdc++.h> | |
#include <bits/extc++.h> | |
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); | |
#define iter(a) a.begin(), a.end() | |
#define riter(a) a.rbegin(), a.rend() | |
#define lsort(a) sort(iter(a)) | |
#define gsort(a) sort(riter(a)) | |
#define pb(a) push_back(a) | |
#define eb(a) emplace_back(a) | |
#define pf(a) push_front(a) | |
#define ef(a) emplace_front(a) | |
#define pob pop_back() | |
#define pof pop_front() | |
#define mp(a, b) make_pair(a, b) | |
#define F first | |
#define S second | |
#define mt make_tuple | |
#define gt(t, i) get<i>(t) | |
#define tomax(a, b) ((a) = max((a), (b))) | |
#define tomin(a, b) ((a) = min((a), (b))) | |
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) | |
#define uni(a) a.resize(unique(iter(a)) - a.begin()) | |
using namespace std; | |
using namespace __gnu_pbds; | |
#define orz | |
#ifdef orz | |
#define printv(a, b) {bool pvaspace=false; \ | |
for(auto pva : a){ \ | |
if(pvaspace) b << " "; pvaspace=true;\ | |
b << pva;\ | |
}\ | |
b << "\n";} | |
#else | |
#define print(a...) | |
void kout() {} | |
template<class T1, class ... T2> void kout(T1 a, T2 ... e) {} | |
#define printv(a, b) | |
#endif | |
typedef long long ll; | |
typedef unsigned long long ull; | |
typedef long double ld; | |
using pii = pair<int, int>; | |
using pll = pair<ll, ll>; | |
using pdd = pair<ld, ld>; | |
using tiii = tuple<int, int, int>; | |
const ll MOD = 1000000007; | |
const ll MAX = 2147483647; | |
template<typename A, typename B> | |
ostream& operator<<(ostream& o, pair<A, B> p){ | |
return o << '(' << p.F << ',' << p.S << ')'; | |
} | |
ll ifloor(ll a, ll b){ | |
if(b < 0) a *= -1, b *= -1; | |
if(a < 0) return (a - b + 1) / b; | |
else return a / b; | |
} | |
ll iceil(ll a, ll b){ | |
if(b < 0) a *= -1, b *= -1; | |
if(a > 0) return (a + b - 1) / b; | |
else return a / b; | |
} | |
struct DSU{ | |
vector<int> dsu; | |
int sz; | |
explicit DSU(int _sz): sz(_sz){ | |
dsu.resize(sz); | |
iota(iter(dsu), 0); | |
} | |
int findDSU(int a){ | |
if(dsu[a] != a) dsu[a] = findDSU(dsu[a]); | |
return dsu[a]; | |
} | |
void unionDSU(int a, int b){ | |
a = findDSU(a); | |
b = findDSU(b); | |
dsu[b] = a; | |
} | |
}; | |
int trans(int x, int y, int n){ | |
int sz = 2 * n + 1; | |
return x * sz + y; | |
} | |
int trans(pii p, int n){ | |
return trans(p.F, p.S, n); | |
} | |
pii convert(int pos, int ti, int n){ | |
int sz = 2 * n + 1; | |
int len = 2 * (sz - ti) - 1 - 4; | |
if(pos == len / 2) return mp(ti + 2, ti + 2); | |
else if(pos < len / 2){ | |
return mp(sz - 1 - pos, ti + 2); | |
} | |
else{ | |
return mp(ti + 2, sz - 1 - (len - pos - 1)); | |
} | |
} | |
vector<pii> dir = {mp(0, 1), mp(1, 0), mp(0, -1), mp(-1, 0)}; | |
string solve_corner(vector<vector<string>>& a, int ti, int tj, int tk, int n){ | |
//cerr << "solve corner\n"; | |
assert(ti == tj); | |
int sz = 2 * n + 1; | |
DSU dsu(sz * sz); | |
int len = 2 * (sz - ti) - 1 - 4; | |
vector<vector<int>> g(sz, vector<int>(sz)); | |
if(tk > 0){ | |
string border; | |
border += a[2][2][0]; | |
for(int i = 2; i < len; i++) border += a[1][1][i - 2 + 1]; | |
border += a[2][2][1]; | |
//cerr << "corner " << tk << " " << ti << " " << border << "\n"; | |
stack<int> st; | |
int pos = 2; | |
string cmd = a[2][2]; | |
for(int i = 0; i < len; i++){ | |
if(border[i] == '0') continue; | |
if(border[i] == '1' && i && border[i - 1] == '1'){ | |
dsu.unionDSU(trans(convert(i, ti, n), n), trans(convert(i - 1, ti, n), n)); | |
continue; | |
} | |
int tmp = (cmd[pos] - '0') * 2 + (cmd[pos + 1] - '0'); | |
pos += 2; | |
if(tmp == 0){ | |
st.push(i); | |
} | |
else if(tmp == 1){ | |
dsu.unionDSU(trans(convert(i, ti, n), n), trans(convert(st.top(), ti, n), n)); | |
st.pop(); | |
} | |
else if(tmp == 2){ | |
// nothing | |
} | |
else if(tmp == 3){ | |
dsu.unionDSU(trans(convert(i, ti, n), n), trans(convert(st.top(), ti, n), n)); | |
} | |
} | |
for(int i = 0; i < 2; i++){ // right | |
for(int j = 0; tj + 2 + j < sz; j++) g[ti + i][tj + 2 + j] = a[i][2][j] - '0'; | |
} | |
for(int i = 0; i < 2; i++){ | |
for(int j = 0; ti + 2 + j < sz; j++) g[ti + 2 + j][tj + i] = a[2][i][j] - '0'; | |
} | |
for(int i = 0; i < 2; i++){ | |
for(int j = 0; j < 2; j++){ | |
g[ti + i][tj + j] = a[i][j][0] - '0'; | |
} | |
} | |
for(int i = 0; i < len; i++){ | |
pii t = convert(i, ti, n); | |
//cerr << "convert " << i << " " << t << "\n"; | |
g[t.F][t.S] = border[i] - '0'; | |
} | |
} | |
else{ | |
for(int i = 0; i < 3; i++){ | |
for(int j = 0; j < 3; j++){ | |
g[ti + i][tj + j] = a[i][j][0] - '0'; | |
} | |
} | |
} | |
//cerr << "test " << tk << " " << ti << "\n"; | |
//for(int i = 0; i < sz; i++) printv(g[i], cerr); | |
for(int i = 0; i < sz; i++){ | |
for(int j = 0; j < sz; j++){ | |
if(i + 1 < sz){ | |
if(g[i][j] && g[i + 1][j]) dsu.unionDSU(trans(i, j, n), trans(i + 1, j, n)); | |
} | |
if(j + 1 < sz){ | |
if(g[i][j] && g[i][j + 1]) dsu.unionDSU(trans(i, j, n), trans(i, j + 1, n)); | |
} | |
} | |
} | |
vector<int> mn(sz * sz, MAX); | |
vector<int> mx(sz * sz); | |
vector<bool> vst(sz * sz); | |
int cnt = bitset<10>(a[2][2].substr(90)).to_ullong(); | |
len = 2 * (sz - ti) - 1; | |
for(int i = 0; i < len; i++){ | |
pii t = convert(i, ti - 2, n); | |
if(g[t.F][t.S] == 0) continue; | |
int p = dsu.findDSU(trans(t, n)); | |
//cerr << "border " << i << " " << t << " " << p << "\n"; | |
mn[p] = min(mn[p], i); | |
mx[p] = max(mx[p], i); | |
if(!vst[p] && tk == n - 1) cnt++; | |
vst[p] = true; | |
} | |
string ans; | |
ans += g[sz - 1][tj] + '0'; | |
ans += g[ti][sz - 1] + '0'; | |
for(int i = 0; i < len; i++){ | |
pii t = convert(i, ti - 2, n); | |
int x = t.F, y = t.S; | |
if(g[x][y] == 0) continue; | |
int l = i, r = i; | |
while(i < len){ | |
pii t2 = convert(i, ti - 2, n); | |
if(g[t2.F][t2.S] == 0) break; | |
r = i; | |
i++; | |
} | |
i--; | |
int p = dsu.findDSU(trans(t, n)); | |
//cerr << "seg " << l << " " << r << " " << p << " " << mn[p] << " " << mx[p] << "\n"; | |
if(mn[p] == l && mx[p] == r) ans += "10"; // 2 | |
else if(mn[p] == l) ans += "00"; // 0 | |
else if(mx[p] == r) ans += "01"; // 1 | |
else ans += "11"; // 3 | |
} | |
while(ans.size() < 100) ans += '0'; | |
for(int i = ti + 1; i < sz; i++){ | |
for(int j = ti + 1; j < sz; j++){ | |
if(g[i][j] == 0) continue; | |
int p = dsu.findDSU(trans(i, j, n)); | |
if(vst[p]) continue; | |
cnt++; | |
vst[p] = true; | |
} | |
} | |
if(tk == n - 1){ | |
string ans = bitset<100>(cnt).to_string(); | |
reverse(iter(ans)); | |
return ans; | |
} | |
string ts = bitset<10>(cnt).to_string(); | |
for(int i = 0; i < 10; i++) ans[90 + i] = ts[i]; | |
return ans; | |
} | |
string solve_corner2(vector<vector<string>>& a, int ti, int tj, int tk, int n){ | |
int sz = 2 * n + 1; | |
string ans; | |
ans += a[0][0][0]; | |
ans += a[1][1][0]; | |
for(int i = 0; ti + 2 + i < sz - 1; i++){ | |
ans += a[2][1][i]; | |
} | |
reverse(ans.begin() + 1, ans.end()); | |
for(int i = 0; ti + 2 + i < sz - 1; i++){ | |
ans += a[1][2][i]; | |
} | |
//cerr << "corner2 " << ti << " " << tj << " " << ans << "\n"; | |
while(ans.size() < 100) ans += '0'; | |
return ans; | |
} | |
string solve_bottom(vector<vector<string>>& a, int ti, int tj, int tk, int n){ | |
string ans(100, '0'); | |
ans[0] = a[0][0][0]; | |
ans[1] = a[1][0][0]; | |
for(int i = 0; 2 + i < 100; i++){ | |
ans[2 + i] = a[2][0][i]; | |
} | |
return ans; | |
} | |
string solve_right(vector<vector<string>>& a, int ti, int tj, int tk, int n){ | |
string ans(100, '0'); | |
ans[0] = a[0][0][0]; | |
ans[1] = a[0][1][0]; | |
for(int i = 0; 2 + i < 100; i++){ | |
ans[2 + i] = a[0][2][i]; | |
} | |
return ans; | |
} | |
string process(vector<vector<string>> a, int ti, int tj, int tk, int n){ | |
int sz = 2 * n + 1; | |
int m = 2 * (n - tk - 1); | |
//cerr << "process " << ti << " " << tj << " " << tk << " " << n << " " << (tk == n - 1) << "\n"; | |
if(ti == m || tj == m){ | |
if(ti == m && tj == m){ | |
string ans = solve_corner(a, ti, tj, tk, n); | |
//cerr << ans << " " << ans.size() << "\n"; | |
return ans; | |
} | |
else if(ti == m) return solve_bottom(a, ti, tj, tk, n); | |
else return solve_right(a, ti, tj, tk, n); | |
} | |
else if(ti == m - 1 || tj == m - 1){ | |
if(ti == m - 1 && tj == m - 1) return solve_corner2(a, ti, tj, tk, n); | |
else if(ti == m - 1) return solve_bottom(a, ti, tj, tk, n); | |
else return solve_right(a, ti, tj, tk, n); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "perm.h" | |
#include <bits/stdc++.h> | |
#include <bits/extc++.h> | |
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); | |
#define iter(a) a.begin(), a.end() | |
#define riter(a) a.rbegin(), a.rend() | |
#define lsort(a) sort(iter(a)) | |
#define gsort(a) sort(riter(a)) | |
#define pb(a) push_back(a) | |
#define eb(a) emplace_back(a) | |
#define pf(a) push_front(a) | |
#define ef(a) emplace_front(a) | |
#define pob pop_back() | |
#define pof pop_front() | |
#define mp(a, b) make_pair(a, b) | |
#define F first | |
#define S second | |
#define mt make_tuple | |
#define gt(t, i) get<i>(t) | |
#define tomax(a, b) ((a) = max((a), (b))) | |
#define tomin(a, b) ((a) = min((a), (b))) | |
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) | |
#define uni(a) a.resize(unique(iter(a)) - a.begin()) | |
using namespace std; | |
using namespace __gnu_pbds; | |
#define orz | |
#ifdef orz | |
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("[" + string(#a) + "] = ", a) | |
void kout() { cerr << endl; } | |
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); } | |
#define printv(a, b) {bool pvaspace=false; \ | |
for(auto pva : a){ \ | |
if(pvaspace) b << " "; pvaspace=true;\ | |
b << pva;\ | |
}\ | |
b << "\n";} | |
#else | |
#define print(a...) | |
void kout() {} | |
template<class T1, class ... T2> void kout(T1 a, T2 ... e) {} | |
#define printv(a, b) | |
#endif | |
typedef long long ll; | |
typedef unsigned long long ull; | |
typedef long double ld; | |
using pii = pair<int, int>; | |
using pll = pair<ll, ll>; | |
using pdd = pair<ld, ld>; | |
using tiii = tuple<int, int, int>; | |
const ll MOD = 1000000007; | |
const ll MAX = 2147483647; | |
template<typename A, typename B> | |
ostream& operator<<(ostream& o, pair<A, B> p){ | |
return o << '(' << p.F << ',' << p.S << ')'; | |
} | |
ll ifloor(ll a, ll b){ | |
if(b < 0) a *= -1, b *= -1; | |
if(a < 0) return (a - b + 1) / b; | |
else return a / b; | |
} | |
ll iceil(ll a, ll b){ | |
if(b < 0) a *= -1, b *= -1; | |
if(a > 0) return (a + b - 1) / b; | |
else return a / b; | |
} | |
vector<int> construct_permutation(ll k){ | |
int l = 1, r = 0; | |
vector<int> ans; | |
for(int i = __lg(k) - 1; i >= 0; i--){ | |
if(1LL << i & k){ | |
ans.eb(r + 1); | |
ans.eb(l - 1); | |
r++; | |
l--; | |
} | |
else{ | |
ans.eb(r + 1); | |
r++; | |
} | |
} | |
for(int& i : ans) i -= l; | |
//printv(ans, cerr); | |
return ans; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment