Submission #1068350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068350		golf	Soccer Stadium (IOI23_soccer)	C++17	19.50 / 100	195 ms	40020 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;
    if (n > 100) {
        cerr << "TOO BIG!" << endl;
        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 && y != j) {a++; A.insert({x, y});}
            if (i < x && y != j) {b++; B.insert({x, y});}
            if (j > y && x != i) {c++; C.insert({x, y});}
            if (j < y && x != i) {d++; D.insert({x, y});}
        }

        int m = cover.size() - min({a, b, c, d});

        if (start == make_pair(4, 3)/*m > max_area*/) {
            cerr << endl << endl;
            print(start, cover);
            cerr << "from: " << i << " " << j << endl;
            cerr << "segment A: " << a << endl;
            print(start, A);
            cerr << "segment B: " << b << endl;
            print(start, B);
            cerr << "segment C: " << c << endl;
            print(start, C);
            cerr << "segment D: " << d << endl;
            print(start, 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;
            

        //     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:174: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]
  174 |         if (max_area == N * N - TREES.size()) return max_area;
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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