제출 #1056429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056429		Ignut	축구 경기장 (IOI23_soccer)	C++17	25 / 100	2785 ms	136448 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 Check() {
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            used[i][j] = false;
    int prev_l = -1, prev_r = -1;
    bool have_sm = false;
    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;

        if (prev_l == -1) {
            prev_l = first;
            prev_r = last;
            continue;
        }
        if (cnt == 0) continue;

        bool sm = false;
        if (first > prev_l || last < prev_r) sm = true;
        bool bg = false;
        if (first < prev_l || last > prev_r) bg = true;
        
        if (sm && bg) return 1;
        if (bg && have_sm) return 1;
        if (sm) have_sm = true;

        prev_l = first;
        prev_r = last;
    }

    prev_l = -1, prev_r = -1;
    have_sm = false;
    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;
     
        if (prev_l == -1) {
            prev_l = first;
            prev_r = last;
            continue;
        }
        if (cnt == 0) continue;

        bool sm = false;
        if (first > prev_l || last < prev_r) sm = true;
        bool bg = false;
        if (first < prev_l || last > prev_r) bg = true;
        
        if (sm && bg) return 1;
        if (bg && have_sm) return 1;
        if (sm) have_sm = true;
        
        prev_l = first;
        prev_r = last;
    }

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (f[i][j] == 1) continue;
            int up = 0;
            for (int ii = i; ii >= 0; ii --) {
                if (f[ii][j] == 1) break;
                up ++;
            }
            int left = 0;
            for (int jj = j; jj >= 0; jj --) {
                if (f[i][jj] == 1) break;
                left ++;
            }
            if (Good(i - up, j - left)) return 1;

            int right = 0;
            for (int jj = j; jj < n; jj ++) {
                if (f[i][jj] == 1) break;
                right ++;
            }
            if (Good(i - up, j + right)) 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;
}

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;
    //     }
    // }
    
    n = N;
    f = F;
    return Check();
}

컴파일 시 표준 에러 (stderr) 메시지

soccer.cpp: In function 'int Check()':
soccer.cpp:155:8: warning: 'j0' may be used uninitialized in this function [-Wmaybe-uninitialized]
  155 |     dfs(i0, j0);
      |     ~~~^~~~~~~~
soccer.cpp:155:8: warning: 'i0' may be used uninitialized in this function [-Wmaybe-uninitialized]

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