Submission #1122365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122365		deera	Soccer Stadium (IOI23_soccer)	C++17	13.50 / 100	4712 ms	1735756 KiB

soccer

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

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

int biggest_stadium(int N, vector<vector<int>> F) {
    int num_trees = 0;
    for (auto i: F) for (int j: i) num_trees += j;

    if (num_trees == 0) {
        return N*N;
    }
    
    if (num_trees == 1) {
        int x, y;
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) 
            if (F[i][j] == 1) {
                x = i, y = j; 
                break;
            }

        return N*N - min(x + 1, N - x) * min(y + 1, N - y);
    }

    // for (auto row: F) {
    //     bool beg = false, end = false;
    //     for (int i: row) {
    //         if (i == 0 && !beg) beg = true;
    //         if (i == 1 &&  beg) end = true;
    //         if (i == 0 &&  end) return 0;
    //     }
    // }

    bool beg, end;
    for (int i = 0; i < N; i++) {
        beg = false, end = false;
        for (int j = 0; j < N; j++) {
            if (F[j][i] == 0 && !beg) beg = true;
            if (F[j][i] == 1 &&  beg) end = true;
            if (F[j][i] == 0 &&  end) return 0;
        }

        beg = false, end = false;
        for (int j = 0; j < N; j++) {
            if (F[i][j] == 0 && !beg) beg = true;
            if (F[i][j] == 1 &&  beg) end = true;
            if (F[i][j] == 0 &&  end) return 0;
        }
    }

    for (int i = 0; i < N; i++) {
        F[i].insert(F[i].begin(), 1);
        F[i].push_back(1);
    }

    F.insert(F.begin(), vector<int>(N + 2, 1));
    F.push_back(vector<int>(N + 2, 1));

    N += 2;


    auto valid = [&](int n) {
        return n >= 0 && n < N;
    };

    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    vector<vector<bool>> seen(N, vector<bool>(N, false));
    queue<tuple<int, int, bool>> q;

    bool f1 = false, f0 = false;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (!f1 && F[i][j] == 1)
            q.push({i, j, true}), f1 = true;
        if (!f0 && F[i][j] == 0)
            q.push({i, j, false}), f0 = true;
    }

    while (!q.empty()) {
        auto [x, y, t] = q.front();
        q.pop();
        seen[x][y] = true;

        for (auto [dx, dy]: dirs) {
            int nx = x + dx, ny = y + dy;
            if (valid(nx) && valid(ny) && !seen[nx][ny] && F[nx][ny] == t)
                q.push({nx, ny, t});
        }
    }

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        if (!seen[i][j]) return 0; // islands!!!

    
    // most extreme zeros
    // Point minx = {N, N}, maxx = {0, 0}, miny = {N, N}, maxy = {0, 0};
    // for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
    //     if (F[i][j] == 0) {
    //         if (i < minx.x) minx = {i, j};
    //         if (i > maxx.x) maxx = {i, j};
    //         if (j < miny.y) miny = {i, j};
    //         if (j > maxy.y) maxy = {i, j};
    //     }
    // }

    // Point points[4] = {minx, maxx, miny, maxy};

    vector<Point> points;

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (F[i][j] == 0) {
            int corners[4][2][2] = {
                {{1, 0}, {0, 1}},
                {{1, 0}, {0, -1}},
                {{-1, 0}, {0, 1}},
                {{-1, 0}, {0, -1}}
            };

            for (auto [a, b]: corners) {
                int ax = i + a[0], ay = j + a[1];
                int bx = i + b[0], by = j + b[1];

                if (F[ax][ay] == 1 && F[bx][by] == 1) {
                    points.push_back(Point(i, j));
                    break;
                }
            }
        }
    }


    for (int i = 0; i < points.size(); i++) for (int j = i + 1; j < points.size(); j++) {
        if (F[points[i].x][points[j].y] + F[points[j].x][points[i].y] == 2) {
            return 0; // 3 or more kicks
        }
    }

    int zeros = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        if (F[i][j] == 0) zeros++;
    }

    return zeros;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < points.size(); i++) for (int j = i + 1; j < points.size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~
soccer.cpp:135:67: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < points.size(); i++) for (int j = i + 1; j < points.size(); j++) {
      |                                                                 ~~^~~~~~~~~~~~~~~
soccer.cpp:25:48: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |         return N*N - min(x + 1, N - x) * min(y + 1, N - y);
      |                                              ~~^~~
soccer.cpp:25:28: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |         return N*N - min(x + 1, N - x) * min(y + 1, N - y);
      |                          ~~^~~

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