제출 #1158647

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

soccer

#include "soccer.h"
#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> p, size;

    void init(int n) {
        p.assign(n + 1, 0);
        size.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) p[i] = i;
    }

    int get(int a) {
        return (p[a] == a ? a : p[a] = get(p[a]));
    }

    void add(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        p[a] = b;
    }
};

void maxs(int &a, int b) {
    if (a < b) a = b;
}

int get(int n, vector<vector<int>> a) {
    dsu ds; ds.init(n * n);
    vector<tuple<int, int, int>> ranges;
    for (int i = 0; i < n; i++) {
        int j = 0;
        while (j < n and a[i][j]) j++;
        if (j == n) continue;
        ranges.emplace_back(i, j, j);
        while (j < n and !a[i][j]) j++;
        get<2>(ranges.back()) = j - 1;

        // if it contains another range?
        while (j < n and a[i][j]) j++;
        if (j != n) return 0;
    }

    // another check
    // cout << ranges.size() << endl;
    for (int j = 0; j < n; j++) {
        int i = 0;
        while (i < n and a[i][j]) i++;
        if (i == n) continue;
        while (i < n and !a[i][j]) i++;
        while (i < n and a[i][j]) i++;
        if (i != n) return 0;
    }

    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    pair<int, int> any;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j]) continue;
            for (int k = 0; k < 4; k++) {
                auto [x, y] = make_pair(i + dx[k], j + dy[k]);
                if (min(x, y) < 0 or max(x, y) >= n) continue;
                if (!a[x][y]) ds.add(i * n + j, x * n + y);
            }
            any = make_pair(i, j);
        }
    }

    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        if (!a[i][j] and ds.get(i * n + j) != ds.get(any.first * n + any.second)) {
            return 0;
        }
    }


    int sum = 0;
    for (int p1 = 0; p1 < ranges.size(); p1++) {
        sum += get<2>(ranges[p1]) - get<1>(ranges[p1]) + 1;
        for (int p2 = 0; p2 < ranges.size(); p2++) {
            auto [i, l, shit1] = ranges[p1];
            auto [j, shit2, r] = ranges[p2];
            bool ok = false;
            ok |= !a[i][r];
            ok |= !a[j][l];
            if (!ok) return 0;
        }
    }
    return sum;
}

int brute(int n, std::vector<std::vector<int>> a) {
    vector<pair<int, int>> pos;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        if (!a[i][j]) pos.emplace_back(i, j);
    }

    int ln = pos.size(), ans = 0;
    for (int bt = 0; bt < (1 << ln); bt++) {
        auto b = a;
        for (int k = 0; k < ln; k++) {
            if (bt & (1 << k)) continue;
            auto [i, j] = pos[k];
            b[i][j] = 1;
        }
        ans = max(ans, get(n, b));
    }
    return ans;
}

bool check(int l1, int r1, int l2, int r2) {
    if (l1 <= l2 and r2 <= r1) return true;
    if (l2 <= l1 and r1 <= r2) return true;
    return false;
}

int biggest_stadium(int n, std::vector<std::vector<int>> a) {
    vector<vector<pair<int, int>>> ranges(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j]) continue;
            if (ranges[i].empty() or ranges[i].back().second + 1 < j) {
                ranges[i].emplace_back(j, j);
            } else {
                ranges[i].back().second++;
            }
        }
    }
    
    map<tuple<int, int, int, int, bool>, int> mp;
    int ans = 0;
    for (int x = 0; x < n; x++) {
        if (ranges[x].empty()) {
            mp.clear();
            continue;
        }
        map<tuple<int, int, int, int, bool>, int> nw;
        for (auto [l, r]: ranges[x]) {
            for (int i = l; i <= r; i++) for (int j = i; j <= r; j++) {
                nw[{i, j, i, j, true}] = j - i + 1;
                int ln = j - i + 1;

                for (auto [it, val]: mp) {
                    auto [sl, sr, l2, r2, tp] = it;

                    if (tp) {
                        // opening -> opening
                        if (i <= l2 and r2 <= j) maxs(nw[{sl, sr, i, j, true}], val + ln);
                    }

                    // opening/closing -> closing
                    if (!(l2 <= i and j <= r2)) continue;
                    if (!check(sl, sr, i, j)) continue;
                    maxs(nw[{sl, sr, i, j, false}], val + ln);
                }
            }
        }
        swap(nw, mp);
        for (auto [it, val]: mp) ans = max(ans, val);
        // for (auto [it, val]: nw) {
        //     cout << get<0>(it) << ' ' << get<1>(it) << ' ' << get<2>(it) << ' ' << val << endl;
        // }
        // cout << endl;
    }
    // cout << ans << endl;
    // assert(ans == brute(n, a));
    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