APIO 2022

game.cpp

#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;
}

mars.cpp

#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);
    }
}

perm.cpp

#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;
}