Submission #1206790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206790		LucasLe	Cell Automaton (JOI23_cell)	C++20	4 / 100	137 ms	102784 KiB

cell

#include <bits/stdc++.h>

template<typename T>
bool minimize(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool maximize(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int MOD = 998244353;

template<typename T>
void add(T &x, T y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

template<typename T>
T bin_pow(T x, T y) {
    T res = 1;
    while (y) {
        if (y & 1)
            res = 1ll * res * x % MOD;
        x = 1ll * x * x % MOD;
        y >>= 1;
    }
    return res;
}

int divi(int x, int y) {
    return x * bin_pow(y, MOD - 2) % MOD;
}

#define fi first
#define se second
#define pii std::pair<int, int>
#define ld long double

int n, q;
pii a[500005];
int query[500005];

void input() {
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i].fi >> a[i].se;
    }
    for (int i = 1; i <= q; ++i) {
        std::cin >> query[i];
    }
}

namespace SUBTASK_12 {
    bool check() {
        for (int i = 1; i <= n; ++i) {
            if (!(abs(a[i].fi) <= 1000 && abs(a[i].se) <= 1000))
                return false;
        }
        for (int i = 1; i <= q; ++i) {
            if (!(query[i] <= 1000))
                return false;
        }
        return true;
    }

    const int maxn = 1e3 + 5;
    const int dx[] = {0, 0, -1, 1};
    const int dy[] = {-1, 1, 0, 0};

    int ans[maxn + 5];
    int dist[5 * maxn + 5][5 * maxn + 5];

    void solve() {
        memset(dist, -1, sizeof dist);
        std::queue<pii> que;
        for (int i = 1; i <= n; ++i) {
            dist[a[i].fi + maxn][a[i].se + maxn] = 0;
            que.push({a[i].fi + maxn, a[i].se + maxn});
        }
        while (!que.empty()) {
            pii tmp = que.front();
            que.pop();
            if (dist[tmp.fi][tmp.se] > maxn)
                continue;
            ans[dist[tmp.fi][tmp.se]]++;
            for (int k = 0; k < 4; ++k) {
                int nx = tmp.fi + dx[k];
                int ny = tmp.se + dy[k];
                if (dist[nx][ny] != -1)
                    continue;
                dist[nx][ny] = dist[tmp.fi][tmp.se] + 1;
                que.push({nx, ny});
            }
        }
        for (int i = 1; i <= q; ++i) {
            std::cout << ans[query[i]] << '\n';
        }
    }
}

namespace SUBTASK_34 {
    bool check() {
        for (int i = 1; i <= n; ++i) {
            if (a[i].fi != a[i].se)
                return false;
        }
        return true;
    }

    void solve() {
        std::vector<int> col;
        for (int i = 1; i <= n; ++i) {
            col.push_back(a[i].fi);
        }
        sort(col.begin(), col.end());

        std::vector<pii> diff;
        for (int i = 1; i < (int)col.size(); ++i) {
            diff.push_back({col[i] - col[i - 1], 0});
            diff.push_back({col[i] - col[i - 1], 2});
        }
        for (int i = 1; i <= q; ++i) {
            diff.push_back({query[i], 1});
        }
        sort(diff.begin(), diff.end());

        /// initial contribution of each square is 4 blocks
        /// each time 2 squares merge together, their total contribution
        /// is 4 blocks instead of 8 blocks, meaning that each of the 2 squares
        /// contribute 2 blocks
        int face = n * 4, ans = 0, prv = 0;
        for (int _ = 0; _ < (int)diff.size(); ++_) {
            int tm = diff[_].fi;
            int ty = diff[_].se;
            if (tm == 0) {
                std::cout << n << '\n';
                continue;
            }
            ans += face * (tm - prv);
            prv = tm;
            if (ty == 1) {
                std::cout << ans << '\n';
            } else {
                /// delete the repeated part of merging 2 squares
                /// ty = 2 means plus 2 squares at each side
                /// face -= 2 reduce the contribution of the square
                ans -= (tm + 1);
                if (ty == 2) ans += 2;
                face -= 2;
            }
        }
    }
}

int main() {
    // std::freopen("input.txt", "r", stdin);
//    std::freopen("i.inp", "r", stdin);
//    std::freopen("sushi.out", "w", stdout);

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    // clock_t start = clock();

    int tc = 1;
//    std::cin >> tc;
    while (tc--) {
        input();
        if (SUBTASK_12::check()) {
            SUBTASK_12::solve();
            return 0;
        }
        if (SUBTASK_34::check()) {
            SUBTASK_34::solve();
            return 0;
        }
    }

    // std::cerr << "Time elapsed: " << clock() - start << " ms\n";
}

• Subtask 1: 4 / 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