Submission #1068218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068218		golf	Soccer Stadium (IOI23_soccer)	C++17	6 / 100	204 ms	32292 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
bool DEBUG = false;

int n;
vector<pair<int, int>> TREES;
vector<vector<bool>> FIELD;

void print(pair<int, int> start, set<pair<int, int>> cover) {
    if (!DEBUG) return;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (start == make_pair(i, j)) cerr << "@";
            else if (cover.count({i, j})) cerr << "+";
            else if (FIELD[i][j]) cerr << "#";
            else cerr << " ";

            cerr << " ";
        }

        cerr << endl;
    }
}


int biggest_stadium(int N, vector<vector<int>> F) {
    n = N;
    FIELD.assign(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        if (F[i][j] == 1) {
            FIELD[i][j] = true;
            TREES.push_back({i, j});
        }

    print({-1, -1}, {});

    if (TREES.size() == 0) return n * n;
    if (TREES.size() == 1) {
        int x = TREES[0].first, y = TREES[0].second;

        n--;
        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);
        n++;

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

    // inefficient
    int max_area = 1;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        if (FIELD[i][j]) continue;
        // if (i != 3 || j != 1) continue; // TODO: REMOVE

        pair<int, int> start = {i, j};

        vector<vector<bool>> used(n, vector<bool>(n, false));
        vector<vector<bool>> done(n, vector<bool>(n, false)); // added to the queue
        set<pair<int, int>> cover;

        for (int x = i; x < n; x++) {
            if (FIELD[x][j]) break;
            used[x][j] = true;
            cover.insert({x, j});
        }

        for (int x = i; x >= 0; x--) {
            if (FIELD[x][j]) break;
            used[x][j] = true;
            cover.insert({x, j});
        }

        for (int y = j; y < n; y++) {
            if (FIELD[i][y]) break;
            used[i][y] = true;
            cover.insert({i, y});
        }

        for (int y = j; y >= 0; y--) {
            if (FIELD[i][y]) break;
            used[i][y] = true;
            cover.insert({i, y});
        }

        queue<pair<int, int>> q;

        q.push(start);
        done[i][j] = true;
        used[i][j] = true;
        cover.insert(start);
        const int dx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        while (!q.empty()) {
            pair<int, int> c = q.front(); q.pop();
            int x = c.first, y = c.second;

            bool spread = used[x][y];
            if (!spread) {
                bool o[4] = {false, false, false, false};
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k][0], ny = y + dx[k][1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (FIELD[nx][ny]) continue;
                    if (used[nx][ny]) o[k] = true;
                }

                if ((o[0] && o[1]) || (o[1] && o[2]) || (o[2] && o[3]) || (o[3] && o[0])) spread = true;
            }

            if (spread) used[x][y] = true;
            if (spread) cover.insert({x, y});
            if (spread) {
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k][0], ny = y + dx[k][1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (FIELD[nx][ny]) continue;
                    if (done[nx][ny]) continue;

                    q.push({nx, ny});
                    done[nx][ny] = true;
                }
            }
        }
        
        int a, b, c, d;
        a = b = c = d = 0;
        set<pair<int, int>> A, B, C, D;

        for (auto [x, y]: cover) {
            if (i >= x) {a++; A.insert({x, y});}
            if (i <= x) {b++; B.insert({x, y});}
            if (j >= y) {c++; C.insert({x, y});}
            if (j <= y) {d++; D.insert({x, y});}
        }

        int m = max({a, b, c, d});
        if (m > max_area) {
            // cerr << endl;
            // cerr << endl;
            // cerr << i << " " << j << endl;
            // print(start, cover);

            cerr << endl;
            cerr << endl;
            cerr << cover.size() << endl;
            cerr << a << " " << b << " " << c << " " << d << endl;
            if (m == a) print(start, A);
            if (m == b) print(start, B);
            if (m == c) print(start, C);
            if (m == d) print(start, D);
            cerr << m << endl;
        }

        max_area = max({max_area, m});
        if (max_area == N * N - TREES.size()) return max_area;
    }

    return max_area;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |         if (max_area == N * N - TREES.size()) return max_area;
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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