제출 #1242345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242345		The_Samurai	축구 경기장 (IOI23_soccer)	C++20	13.50 / 100	4241 ms	33096 KiB

soccer

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

void maxs(short &a, short b) { a = max(a, b); }

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 sz1 = n * n / 2, sz2 = n * n - n * n / 2;
    vector<short> mx(1 << sz1);
    for (ll bt = 0; bt < (1 << sz1); bt++) {
        bitset<49> act;
        act.flip();
        for (int i = 0; i < sz1; i++) if (bt >> i & 1) act &= out[i];
        if ((act.to_ullong() & bt) == bt) mx[bt] = __builtin_popcountll(bt);
        for (int i = 0; i < sz1; i++) {
            if (!(bt >> i & 1)) maxs(mx[bt | (1 << i)], mx[bt]);
        }
    }
    int ans = 0;
    for (ll bt = 0; bt < (1 << sz2); bt++) {
        bitset<49> act;
        act.flip();
        for (int i = 0; i < sz2; i++) {
            if (bt >> i & 1) act &= out[i + sz1];
        }
        if (((act.to_ullong() >> sz1) & bt) != bt) continue;
        int bt2 = 0;
        for (int i = 0; i < sz1; i++) {
            if (!act[i]) continue;
            if (((out[i].to_ullong() >> sz1) & bt) == bt) bt2 |= 1 << i;
        }
        ans = max(ans, __builtin_popcountll(bt) + mx[bt2]);
    }

    return ans;
}

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