제출 #1066344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066344		deera	Soccer Stadium (IOI23_soccer)	C++17	24 / 100	4577 ms	44112 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

struct Pos {
    int x, y;
    Pos(int x, int y) : x(x), y(y) {}
};

bool FIELD[2001][2001] = {0};
bool empty(int a, int b, int x, int y) {
    assert(a == x || b == y); // only 1d queries
    if (a == x)
        for (int i = min(b, y); i <= max(b, y); i++)
            if (FIELD[a][i]) return false;
    if (b == y) 
        for (int i = min(a, x); i <= max(a, x); i++)
            if (FIELD[i][b]) return false;
    return true;
}

set<int> USED;
map<int, set<int>> G;
vector<int> NODES;

int biggest_stadium(int N, vector<vector<int>> F) {
    vector<Pos> trees;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (F[i][j] == 1) trees.push_back({i, j});
        FIELD[i][j] = F[i][j];
    }

    for (auto tree : trees) {
        cerr << tree.x << " " << tree.y << endl;
    }

    if (trees.size() == 0) return N * N;
    if (trees.size() == 1) {
        int x = trees[0].x, y = trees[0].y;

        int n = N - 1;
        int a = (abs(x - 0) + 1) * (abs(y - 0) + 1);
        int b = (abs(x - 0) + 1) * (abs(y - n) + 1);
        int c = (abs(x - n) + 1) * (abs(y - 0) + 1);
        int d = (abs(x - n) + 1) * (abs(y - n) + 1);


        return N * N - min({a, b, c, d});
    }

    const int MAXN = 500;

    set<set<pair<int, int>>> cover;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (FIELD[i][j] == 1) continue;
        
        const int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        // x, y and direction and the kick
        // 0 = first kick, 1 = second kick
        queue<tuple<int, int, int, bool>> q;
        bool used[MAXN][MAXN][4][2] = {0};
        bool visited[MAXN][MAXN] = {0};
        set<pair<int, int>> vis;

    
        visited[i][j] = true;
        vis.insert({i, j});
        for (int d = 0; d < 4; d++) {
            used[i][j][d][0] = true;
            q.push({i, j, d, 0});
        }

        while (!q.empty()) {
            auto [x, y, d, k] = q.front(); q.pop();
            x += DIRS[d][0];
            y += DIRS[d][1];

            if (x < 0 || x >= N || y < 0 || y >= N) continue;
            if (FIELD[x][y]) continue;
            if (used[x][y][d][k]) continue;

            visited[x][y] = true;
            vis.insert({x, y});

            used[x][y][d][k] = true;
            q.push({x, y, d, k});

            if (k == true) continue;
            for (int d = 0; d < 4; d++) {
                used[x][y][d][1] = true;
                q.push({x, y, d, 1});
            }
        }

        for (auto [x, y] : vis) {
            int a = i * N + j;
            int b = x * N + y;

            G[a].insert(b);
            G[b].insert(a);
            NODES.push_back(a);
            NODES.push_back(b);
        }

        cover.insert(vis);
        
        cerr << "\ncoverage from " << i << " " << j << endl;
        for (int a = 0; a < N; a++) {
            for (int b = 0; b < N; b++) {
                if (a == i && b == j) cerr << "@";
                else if (FIELD[a][b]) cerr << "#";
                else if (visited[a][b]) cerr << "+";
                else cerr << " ";
                cerr << " ";
            }
            cerr << '\n';
        }
    }

    if (N == 3) {
        vector<set<int>> max_comps;
        deque<set<int>> comps;
        set<set<int>> done;

        for (int node: NODES) comps.push_back({node});
        for (int node: NODES) done.insert({node});

        while (!comps.empty()) {
            set<int> comp = comps.front(); comps.pop_front();

            bool changed = false;
            for (int node: NODES) {
                if (comp.count(node)) continue;
                set<int> children = G[node];

                // check if comp is a subset of children
                bool is_subset = true;
                for (int c : comp) {
                    if (!children.count(c)) {
                        is_subset = false;
                        break;
                    }
                }

                if (is_subset) {
                    changed = true;
                    set<int> new_comp = comp;
                    new_comp.insert(node);
                    
                    if (!done.count(new_comp)) {
                        done.insert(new_comp);
                        comps.push_back(new_comp);
                    }
                }
            }

            if (!changed) {
                max_comps.push_back(comp);
            }
        }


        for (auto comp: max_comps) {
            cerr << endl;
            cerr << "component of size " << comp.size() << endl;
            for (int a = 0; a < N; a++) {
                for (int b = 0; b < N; b++) {
                    if (FIELD[a][b]) cerr << "#";
                    else if (comp.count(a * N + b)) cerr << "+";
                    else cerr << " ";
                    cerr << " ";
                }
                cerr << '\n';
            }
        }

        int max_size = 0;
        for (auto comp: max_comps) 
            max_size = max(max_size, (int)comp.size());

        return max_size;
    }


    for (int a = 0; a < N; a++) for (int b = 0; b < N; b++) {
        for (int x = 0; x < N; x++) for (int y = 0; y < N; y++) {
            // going throgh (a, y)
            if (a == x && b == y) continue;
            if (FIELD[a][b] || FIELD[x][y]) continue;
            if ((empty(a, b, a, y) && empty(x, y, a, y)) 
              || empty(a, b, x, b) && empty(x, y, x, b)) {
                continue;
            } else {return 0;}
        }
    }

    return N * N - trees.size();
}

컴파일 시 표준 에러 (stderr) 메시지

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:191:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  191 |               || empty(a, b, x, b) && empty(x, y, x, b)) {
      |                  ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

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