Submission #741955

#	Time	Username	Problem	Language	Result	Execution time	Memory
741955		t6twotwo	Mars (APIO22_mars)	C++17	54 / 100	502 ms	3664 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
array<int, 4> get(int N, int K, int i, int j) {
    int M = N - 2 * K;
    int x = N / M;
    int y = N % M;
    if (i < y && j < y) {
        return {i * (x + 1), j * (x + 1), x + 1, x + 1};
    } else if (i < y) {
        return {i * (x + 1), y * (x + 1) + (j - y) * x, x + 1, x};
    } else if (j < y) {
        return {y * (x + 1) + (i - y) * x, j * (x + 1), x, x + 1};
    } else {
        return {y * (x + 1) + (i - y) * x, y * (x + 1) + (j - y) * x, x, x};
    }
}
constexpr int dx[] = {0, 0, -1, 1};
constexpr int dy[] = {-1, 1, 0, 0};
int cnt(vector<vector<char>> &g) {
    int n = g.size(), ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == '0') {
                continue;
            }
            ans++;
            queue<pair<int, int>> q;
            g[i][j] = '0';
            q.emplace(i, j);
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (min(nx, ny) >= 0 && max(nx, ny) < n && g[nx][ny] == '1') {
                        g[nx][ny] = '0';
                        q.emplace(nx, ny);
                    }
                }
            }
        }
    }
    return ans;
}
string process(vector<vector<string>> a, int X, int Y, int K, int N) {
    vector g(2 * N + 1, vector<char>(2 * N + 1));
    for (int i = X; i < X + 3; i++) {
        for (int j = Y; j < Y + 3; j++) {
            auto [s, t, u, v] = get(2 * N + 1, K, i, j);
            for (int x = s; x < s + u; x++) {
                for (int y = t; y < t + v; y++) {
                    assert(x <= 2 * N && y <= 2 * N);
                    g[x][y] = a[i - X][j - Y][v * (x - s) + (y - t)];
                }
            }
        }
    }
    string ans(100, '0');
    if (K == N - 1) {
        int land = cnt(g);
        for (int i = 0; i < 30; i++) {
            if (land >> i & 1) {
                ans[i] = '1';
            }
        }
    } else {
        auto [s, t, u, v] = get(2 * N + 1, K + 1, X, Y);
        for (int i = s; i < s + u; i++) {
            for (int j = t; j < t + v; j++) {
                assert(i <= 2 * N && j <= 2 * N);
                ans[v * (i - s) + (j - t)] = g[i][j];
            }
        }
    }
    return ans;
}

• 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