제출 #1311782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311782		madamadam3	Cell Automaton (JOI23_cell)	C++20	0 / 100	8109 ms	583448 KiB

cell

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;

struct State {
    int t = 0;
    set<pi> black, gray;

    State() {};
    State(vi &x, vi &y) {
        for (int i = 0; i < x.size(); i++) black.insert({x[i], y[i]});
    }
    State(int T, set<pi> &B, set<pi> &G) {
        t = T; black = B; gray = G;
    }

    State next() {
        set<pi> ng = black, nb;
        for (auto el : black) {
            for (auto d : vector<pi>({{0, -1}, {0, 1}, {-1, 0}, {1, 0}})) {
                pi nx = {el.first + d.first, el.second + d.second};
                if (!black.count(nx) && !gray.count(nx)) nb.insert(nx);
            }
        }

        return State(t+1, nb, ng);
    }

    void output(int M = -1) {
        if (M == -1) {
            for (auto el : black) M = max({M, abs(el.first), abs(el.second)});
            for (auto el : gray)  M = max({M, abs(el.first), abs(el.second)});
        }

        for (int i = -M; i <= M; i++) {
            for (int j = -M; j <= M; j++) {
                if (black.count({i, j})) cout << 1;
                else if (gray.count({i, j})) cout << 2;
                else cout << 0;
                cout << " ";
            }
            cout << "\n";
        }
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, q; cin >> n >> q;
    vector<int> x(n), y(n); for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    auto cur = State(y, x);

    vector<int> ans(1, n);
    int prev = n, cnt = 1;

    while (cnt < n*n) {
        cur = cur.next();
        ans.push_back(cur.black.size());

        int r = cur.black.size() - cur.gray.size();
        if (r == prev) cnt++;
        else prev = r, cnt = 1;
    }

    int ratio = (ans[ans.size() - 1] - ans[ans.size() - 2]);
    while (q--) {
        int t; cin >> t;
        if (t < ans.size()) cout << ans[t] << "\n";
        else cout << ans.back() + ratio * (t - ans.size() + 1) << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 26