Submission #739185

#	Time	Username	Problem	Language	Result	Execution time	Memory
739185		PixelCat	Mars (APIO22_mars)	C++17	0 / 100	1 ms	220 KiB

mars

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

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11