Submission #1231665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231665		ericl23302	Soccer Stadium (IOI23_soccer)	C++20	0 / 100	4593 ms	320 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

bool check2(vector<vector<bool>> &includes, int a, int b, int c, int d) {
    if (a == c) {
        for (int i = min(b, d) + 1; i < max(b, d); ++i) {
            if (!includes[a][i]) return false;
        }
        return true;
    } else if (b == d) {
        for (int i = min(a, c) + 1; i < max(a, c); ++i) {
            if (!includes[i][b]) return false;
        }
        return true;
    } 

    // x first
    if (c < a) swap(a, c), swap(b, d);
    bool ok = true;
    for (int i = a; i <= c; ++i) {
        if (!includes[i][b]) {
            ok = false;
            break;
        }
    }
    if (ok) {
        for (int i = min(b, d); i <= max(b, d); ++i) {
            if (!includes[c][i]) {
                ok = false;
                break;
            }
        }
    }
    if (ok) return true;

    // y first
    ok = true;
    if (d < b) swap(a, c), swap(b, d);
    for (int i = b; i <= d; ++i) {
        if (!includes[a][i]) {
            ok = false; 
            break;
        }
    }
    if (ok) {
        for (int i = min(a, c); i <= max(a, c); ++i) {
            if (!includes[i][d]) {
                ok = false;
                break;
            }
        }
    }

    return ok;
}

bool check(vector<vector<bool>> &includes) {
    int n = includes.size();
    for (int a = 0; a < n; ++a) {
        for (int b = 0; b < n; ++b) {
            if (!includes[a][b]) continue;
            for (int c = a; c < n; ++c) {
                for (int d = 0; d < n; ++d) {
                    if (a == c && d == 0) {
                        d = b;
                        continue;
                    }
                    if (!includes[c][d]) continue;
                    if (!check2(includes, a, b, c, d)) return false;
                }
            }
        }
    }

    return true;
}

int solve(vector<vector<bool>> &includes, int cnt) {
    int n = includes.size();
    if (cnt == 1) return 1;
    if (check(includes)) return cnt;
    int res = 0;
    for (int a = 0; a < n; ++a) {
        for (int b = 0; b < n; ++b) {
            if (!includes[a][b]) continue;
            includes[a][b] = false;
            res = max(res, solve(includes, cnt - 1));
            includes[a][b] = true;
        }
    }

    return res;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    int cnt = 0;
    vector<vector<bool>> f(N, vector<bool>(N, false));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (!F[i][j]) ++cnt;
            f[i][j] = !F[i][j];
        }
    }
    
    return solve(f, cnt);
}

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