oj.uz

Submission #1068195

# Submission time Handle Problem Language Result Execution time Memory
1068195 2024-08-21T08:25:56 Z golf Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 36816 KB 
#include <bits/stdc++.h>
using namespace std;

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

void print(pair<int, int> start, set<pair<int, int>> cover) {
    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});
    }

    if (n > 100) return 0; // TODO: REMOVE

    // 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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 19 ms 348 KB ok
8 Correct 496 ms 2900 KB ok
9 Execution timed out 4553 ms 36816 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Partially correct 0 ms 348 KB partial
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 1 ms 348 KB ok
13 Incorrect 1 ms 348 KB wrong
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Partially correct 0 ms 348 KB partial
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 1 ms 348 KB ok
14 Incorrect 1 ms 348 KB wrong
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 1 ms 348 KB ok
16 Incorrect 1 ms 348 KB wrong
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 344 KB ok
15 Correct 1 ms 348 KB ok
16 Incorrect 1 ms 348 KB wrong
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 19 ms 348 KB ok
9 Correct 496 ms 2900 KB ok
10 Execution timed out 4553 ms 36816 KB Time limit exceeded
11 Halted 0 ms 0 KB -