Submission #572668

#	Time	Username	Problem	Language	Result	Execution time	Memory
572668		tabr	Mars (APIO22_mars)	C++17	14 / 100	23 ms	2292 KiB

mars

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

string count_islands(vector<string> s) {
    int n = (int) s.size();
    dsu uf(n * n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (s[i][j] == '1' && s[i][j + 1] == '1') {
                uf.unite(i * n + j, i * n + j + 1);
            }
        }
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '1' && s[i + 1][j] == '1') {
                uf.unite(i * n + j, i * n + j + n);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '1' && uf.root(i * n + j)) {
                ans++;
            }
        }
    }
    string res(100, '0');
    for (int i = 0; i < 20; i++) {
        if (ans & (1 << i)) {
            res[i] = '1';
        }
    }
    return res;
}

vector<int> count_groups(int k, int n) {
    if (k == 0) {
        vector<int> g;
        for (int i = 0; i < 3; i++) {
            g.emplace_back((2 * n + 1) * (i + 1) / 3 - (2 * n + 1) * i / 3);
        }
        return g;
    }
    auto g = count_groups(k - 1, n);
    for (int z = 0; z < 2; z++) {
        for (int i = 0; i < 3; i++) {
            if (g[i] > 1) {
                g[i]--;
                break;
            }
        }
    }
    return g;
}

vector<int> move_from(int k, int n) {
    assert(0 <= k && k < n - 1);
    auto g = count_groups(k, n);
    int l = 2 * (n - k) - 1;
    vector<int> c;
    assert(g[0] + g[1] + g[2] == l + 2);
    for (int z = 0; z < 2; z++) {
        for (int i = 0; i < 3; i++) {
            if (g[i] > 1) {
                g[i]--;
                c.emplace_back(i);
                break;
            }
        }
    }
    for (int i = 0; i < 2; i++) {
        c[i] = g[c[i]];
    }
    for (int i = 0; i < l; i++) {
        c.emplace_back(i);
    }
    sort(c.begin(), c.end());
    return c;
}

vector<vector<vector<pair<int, int>>>> original_pos(int k, int n) {
    int l = 2 * (n - k) + 1;
    vector<vector<vector<pair<int, int>>>> res(l, vector<vector<pair<int, int>>>(l));
    if (k == 0) {
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                res[i][j].emplace_back(i, j);
            }
        }
        return res;
    }
    // make l x l board from (l + 2) x (l + 2)
    // (x, y) <- (nx, ny) such that c[nx] == x and c[ny] == y
    auto t = original_pos(k - 1, n);
    auto c = move_from(k - 1, n);
    for (int x = 0; x < l; x++) {
        for (int y = 0; y < l; y++) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (x == c[x + i] && y == c[y + j]) {
                        for (auto p : t[x + i][y + j]) {
                            res[x][y].emplace_back(p);
                        }
                    }
                }
            }
        }
    }
    return res;
}

string process(vector<vector<string>> a, int x, int y, int k, int n) {
    auto t = original_pos(k, n);
    if (k == n - 1) {
        vector<string> s(2 * n + 1, string(2 * n + 1, '0'));
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int id = 0; id < (int) t[i][j].size(); id++) {
                    s[t[i][j][id].first][t[i][j][id].second] = a[i][j][id];
                }
            }
        }
        debug(s);
        return count_islands(s);
    }
    auto c = move_from(k, n);
    string res;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (x == c[x + i] && y == c[y + j]) {
                res += a[i][j].substr(0, t[x + i][y + j].size());
            }
        }
    }
    assert(res.size() <= 100);
    res += string(100 - res.size(), '0');
    return res;
}

#ifdef tabr
static void WA(string msg) {
    cout << "WA: " << msg << endl;
    exit(0);
}

static long long to_longlong(string s) {
    long long ans = 0;
    for (int i = (int) s.size() - 1; i >= 0; i--)
        ans = (ans * 2) + s[i] - '0';
    return ans;
}

int main() {
    int t;
    assert(scanf("%d", &t) == 1);
    while (t--) {
        int n;
        assert(scanf("%d", &n) == 1);
        vector<vector<char>> s(2 * n + 1, vector<char>(2 * n + 1));
        for (int i = 0; i < 2 * n + 1; i++)
            for (int j = 0; j < 2 * n + 1; j++)
                assert(scanf(" %c", &s[i][j]) == 1);
        vector<vector<string>> h(2 * n + 1, vector<string>(2 * n + 1, string(100, '0')));
        for (int i = 0; i < 2 * n + 1; i++)
            for (int j = 0; j < 2 * n + 1; j++)
                h[i][j][0] = s[i][j];
        vector<vector<string>> subarr(3, vector<string>(3));
        for (int k = 0; k < n; k++) {
            int m = 2 * (n - k - 1);
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= m; j++) {
                    for (int y = 0; y < 3; y++) {
                        for (int x = 0; x < 3; x++) {
                            subarr[y][x] = h[i + y][j + x];
                        }
                    }
                    h[i][j] = process(subarr, i, j, k, n);

                    if (h[i][j].size() != 100) WA("Invalid return length");
                    for (int l = 0; l < 100; l++)
                        if (h[i][j][l] != '0' && h[i][j][l] != '1') WA("Invalid return");
                }
            }
        }
        printf("%lld\n", to_longlong(h[0][0]));
    }
}
#endif

• Subtask 1: 6 / 6
• Subtask 2: 8 / 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