Submission #1056147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056147		Ignut	Soccer Stadium (IOI23_soccer)	C++17	1.50 / 100	165 ms	51764 KiB

soccer

/* Ignut
started: 13.08.2024
now: 13.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int MAXN = 2222;
int n;
vector<vector<int>> f;
 
bool used[MAXN][MAXN];
 
vector<pair<int, int>> delta = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
 
bool Good(int i, int j) {
    return i >= 0 && j >= 0 && i < n && j < n && f[i][j] == 0 && !used[i][j];
}
 
int cnt = 0;
void dfs(int i, int j) {
    cnt ++;
    used[i][j] = true;
    for (auto [di, dj] : delta) {
        int ci = i + di, cj = j + dj;
        if (Good(ci, cj)) {
            dfs(ci, cj);
        }
    }
}
 
int biggest_stadium(int N, vector<vector<int>> F) {
    // for (int i = 0; i < N; i ++) {
    //     for (int j = 0; j < N; j ++) {
    //         if (F[i][j] == 0) continue;
    //         int mn = N * N;
    //         mn = min(mn, (i + 1) * (j + 1));
    //         mn = min(mn, (N - i) * (N - j));
    //         mn = min(mn, (N - i) * (j + 1));
    //         mn = min(mn, (i + 1) * (N - j));
    //         return N * N - mn;
    //     }
    // }
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            used[i][j] = false;
 
    n = N;
    f = F;
    for (int i = 0; i < N; i ++) {
        int first = -1, last = -1, cnt = 0;
        for (int j = 0; j < N; j ++) {
            if (F[i][j] == 1) continue;
            if (first == -1) first = j;
            last = j;
            cnt ++;
        }
        if (cnt > 0 && cnt != last - first + 1) return 1;
    }
    for (int j = 0; j < N; j ++) {
        int first = -1, last = -1, cnt = 0;
        for (int i = 0; i < N; i ++) {
            if (F[i][j] == 1) continue;
            if (first == -1) first = i;
            last = i;
            cnt ++;
        }
        if (cnt > 0 && cnt != last - first + 1) return 1;
    }
 
    int i0, j0;
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            if (F[i][j] == 0)
                i0 = i, j0 = j;
 
  	cnt = 0;
    dfs(i0, j0);
 
    int sum = N * N;
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            sum -= F[i][j];
 
    if (cnt != sum) return 1;
    
    return sum;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:97:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |     for (int i = 0; i < N; i ++)
      |     ^~~
soccer.cpp:102:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  102 |    cnt = 0;
      |    ^~~
soccer.cpp:103:8: warning: 'i0' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |     dfs(i0, j0);
      |     ~~~^~~~~~~~
soccer.cpp:103:8: warning: 'j0' may be used uninitialized in this function [-Wmaybe-uninitialized]

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