Submission #1242293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242293		The_Samurai	Soccer Stadium (IOI23_soccer)	C++20	8 / 100	2146 ms	416 KiB

soccer

#include "soccer.h"
#include "bits/stdc++.h"
using namespace std;
const int inf = 1e9;

int biggest_stadium(int n, std::vector<std::vector<int>> f) {
    vector<bitset<49>> out(n * n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) f[i][j] = !f[i][j];

    const vector<int> dx = {1, -1, 0, 0};
    const vector<int> dy = {0, 0, 1, -1};
    auto get_dist = [&](int ri, int rj) -> vector<int> {
        vector<int> dist(n * n, inf);
        dist[ri * n + rj] = 0;
        queue<pair<int, int>> q;
        q.emplace(ri, rj);

        auto add = [&](int i, int j, int d) -> void {
            if (dist[i * n + j] > d) {
                dist[i * n + j] = d;
                q.emplace(i, j);
            }
        };

        while (!q.empty()) {
            auto [i, j] = q.front(); q.pop();
            for (int k = i; k >= 0 and f[k][j]; k--) add(k, j, dist[i * n + j] + 1);
            for (int k = i; k < n and f[k][j]; k++) add(k, j, dist[i * n + j] + 1);
            for (int k = j; k >= 0 and f[i][k]; k--) add(i, k, dist[i * n + j] + 1);
            for (int k = j; k < n and f[i][k]; k++) add(i, k, dist[i * n + j] + 1);
        }
        return dist;
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int id = i * n + j;
            out[id] = bitset<49>();
            if (f[i][j] == 0) continue;
            auto dist = get_dist(i, j);
            for (int k = 0; k < n * n; k++) if (dist[k] <= 2) out[id][k] = true;
        }
    }

    const int N = n * n;
    int ans = 0;
    for (int bt = 0; bt < (1 << N); bt++) {
        bitset<49> act;
        act.flip();
        for (int i = 0; i < N; i++) {
            if (bt >> i & 1) act &= out[i];
        }
        if ((act.to_ullong() & bt) == bt) ans = max(ans, __builtin_popcount(bt));
    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30