Submission #728675

#	Time	Username	Problem	Language	Result	Execution time	Memory
728675		vjudge1	Mars (APIO22_mars)	C++17	54 / 100	1774 ms	16064 KiB

mars

#include "mars.h"

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> f[30][30][30];
vector<pair<int, int>> trace[30][30][30];
int g[30][30][30];
int done[30][30][30];

std::string process(std::vector<std::vector<std::string>> a, int i, int j, int k, int n) {
        k++;
        auto fill = [&](int x, int y, int z, int a, int b) {
                f[z][x][y].clear();
                if (k == n) trace[z][x][y].clear();
                g[z][x][y] = 0;
                for (int ii = x; ii < x + 3; ii++) {
                        for (int jj = y; jj < y + 3; jj++) {
                                if (x / a != ii / b) continue;
                                if (y / a != jj / b) continue;
                                if (done[z - 1][ii][jj] == 0) {
                                        f[z][x][y].emplace_back(ii, jj);
                                        if (k == n) trace[z][x][y].insert(trace[z][x][y].end(), trace[z - 1][ii][jj].begin(), trace[z - 1][ii][jj].end());
                                        g[z][x][y] += g[z - 1][ii][jj];
                                        done[z - 1][ii][jj] = 1;
                                }
                        }
                }
        };
        if (k != n) {
                memset(done, 0, sizeof done);
                memset(g, 0, sizeof g);
                for (int ii = 0; ii <= n * 2; ii++) {
                        for (int jj = 0; jj <= n * 2; jj++) {
                                trace[0][ii][jj] = {{ii, jj}};
                                g[0][ii][jj] = 1;
                        }
                }

                int cur_i = i / (((n - k) * 2) / 3 + 1);
                int cur_j = j / (((n - k) * 2) / 3 + 1);
                for (int kk = 1; kk <= k; kk++) {
                        int mm = (n - kk) * 2;
                        int cur_size = mm / 3 + 1;
                        int last_size = (mm + 2) / 3 + 1;
                        for (int ii = cur_i * cur_size; ii <= mm && ii < (cur_i + 1) * cur_size; ii++) {
                                for (int jj = cur_j * cur_size; jj <= mm && jj < (cur_j + 1) * cur_size; jj++) {
                                        fill(ii, jj, kk, cur_size, last_size);
                                }
                        }
                }

                string s = "";
                for (pair<int, int>& p : f[k][i][j]) {
                        int ii = p.first;
                        int jj = p.second;
                        int x = ii - i;
                        int y = jj - j;
                        for (int z = 0; z < g[k - 1][ii][jj]; z++) {
                                s += a[x][y][z];
                        }
                }
                while (s.size() < 100) s += '0';
                assert(s.size() == 100);
                return s;
        }

        memset(done, 0, sizeof done);
        memset(g, 0, sizeof g);
        for (int ii = 0; ii <= n * 2; ii++) {
                for (int jj = 0; jj <= n * 2; jj++) {
                        trace[0][ii][jj] = {{ii, jj}};
                        g[0][ii][jj] = 1;
                }
        }

        for (int kk = 1; kk <= k; kk++) {
                int mm = (n - kk) * 2;
                int cur_size = mm / 3 + 1;
                int last_size = (mm + 2) / 3 + 1;
                for (int ii = 0; ii <= mm; ii++) {
                        for (int jj = 0; jj <= mm; jj++) {
                                fill(ii, jj, kk, cur_size, last_size);
                        }
                }
        }
        k--;
        vector<vector<int>> map(n * 2 + 1, vector<int>(n * 2 + 1, 0));

        for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                        for (int z = 0; z < g[k][i][j]; z++) {
                                int ii = trace[k][i][j][z].first;
                                int jj = trace[k][i][j][z].second;
                                map[ii][jj] = a[i][j][z] - '0';
                        }
                }
        }

        int dr[] = {-1, 0, +1, 0};
        int dc[] = {0, -1, 0, +1};

        int res = 0;
        for (int i = 0; i <= n * 2; i++) {
                for (int j = 0; j <= n * 2; j++) {
                        if (map[i][j] == 1) {
                                res++;
                                queue<pair<int, int>> q;
                                q.emplace(i, j);
                                map[i][j] = 0;
                                while (q.size()) {
                                        int ii = q.front().first;
                                        int jj = q.front().second;
                                        q.pop();
                                        for (int id = 0; id < 4; id++) {
                                                int ni = ii + dr[id];
                                                int nj = jj + dc[id];
                                                if (ni < 0 || nj < 0 || ni > n * 2 || nj > n * 2 || map[ni][nj] == 0) continue;
                                                q.emplace(ni, nj);
                                                map[ni][nj] = 0;
                                        }
                                }
                        }
                }
        }
        string s = "";
        while (s.size() < 100) s += res % 2 + '0', res /= 2;
        return s;
}

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