Submission #1078863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078863		PoPularPlusPlus	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	323 ms	43860 KiB

soccer

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

#define ll long long
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vf first
#define vs second

int dx[4] = {1 , -1 , 0 , 0} , dy[4] = {0 , 0 , -1 , 1};

int biggest_stadium(int n, vector<vector<int>> f){
    bool vis[n][n];
    memset(vis,0,sizeof vis);
    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(f[i][j] == 0 && !vis[i][j]){
                cnt++;
                vis[i][j] = 1;
                queue<pair<int,int>> q;
                q.push(mp(i , j));
                while(q.size()){
                    int r = q.front().vf , c = q.front().vs;
                    q.pop();
                    for(int tp = 0; tp < 4; tp++){
                        int nr = r + dx[tp] , nc = c + dy[tp];
                        if(nr >= 0 && nr < n && nc >= 0 && nc < n && f[nr][nc] == 0 && vis[nr][nc] == 0){
                            vis[nr][nc] = 1;
                            q.push(mp(nr,nc));
                        }
                    }
                }
            }
        }
    }

    if(cnt > 1)return 0;

    int mx_col[n] , mn_col[n];
    int pre_mx[n] , pre_mn[n] , suf_mx[n], suf_mn[n];
    for(int i = 0; i < n; i++){
        mx_col[i] = mn_col[i] = -1;
        for(int j = 0; j < n; j++){
            if(f[i][j] == 0){
                if(mx_col[i] == -1){
                    mx_col[i] = mn_col[i] = j;
                }
                else {
                    mx_col[i] = j;
                }
            }
        }

        for(int j = 0; j < n && mx_col[i] != -1; j++){
            if(f[i][j] == 1){
                if(j > mn_col[i] && j < mx_col[i]){
                    return 0;
                }
            }
        }
    }

    pre_mx[0] = mx_col[0];
    pre_mn[0] = mn_col[0];
    for(int i = 1; i < n; i++){
        if(pre_mn[i-1] == -1)pre_mn[i] = mn_col[i];
        else if(mn_col[i] == -1)pre_mn[i] = pre_mn[i-1];
        else pre_mn[i] = min(pre_mn[i-1] , mn_col[i]);

        pre_mx[i] = max(pre_mx[i-1] , mx_col[i]);
    }

    suf_mx[n-1] = mx_col[n-1];
    suf_mn[n-1] = mn_col[n-1];
    for(int i = n - 2; i >= 0; i--){
        if(suf_mn[i+1] == -1)suf_mn[i] = mn_col[i];
        else if(mn_col[i] == -1)suf_mn[i] = suf_mn[i+1];
        else suf_mn[i] = min(suf_mn[i+1] , mn_col[i]);

        suf_mx[i] = max(suf_mx[i+1] , mx_col[i]);
    }

    int ans = 0;

    int best_l[n] , best_r[n];
    for(int j = 0; j < n; j++){
        best_l[j] = -1;
        best_r[j] = -1;
        for(int i = 0; i < n; i++){
            if(f[i][j] == 0){
                if(best_l[j] == -1)best_l[j] = i;
                best_r[j] = i;
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(f[i][j] == 1){
                if(best_l[j] != -1 && i > best_l[j] && i < best_r[j]){
                    return 0;
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(f[i][j] == 0){
                ans++;

                int left = best_l[j] - 1 , right = best_r[j] + 1;
                int r_min = mn_col[i] , r_max = mx_col[i];
                bool ok = 1;
                if(left >= 0){
                    if(pre_mn[left] != -1 && pre_mn[left] < r_min){
                        ok = 0;
                    }
                    if(pre_mx[left] != -1 && pre_mx[left] > r_max){
                        ok = 0;
                    }
                }
                if(right < n){
                    if(suf_mn[right]!= -1 && suf_mn[right] < r_min){
                        ok = 0;
                    }
                    if(suf_mx[right]!=-1 && suf_mx[right] > r_max){
                        ok = 0;
                    }
                }

                if(ok == 0){
                    return 0;
                }
            }
        }
    }
    return ans;
}

• 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