Submission #1242366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242366		Hamed_Ghaffari	Soccer Stadium (IOI23_soccer)	C++20	6 / 100	197 ms	47620 KiB

soccer

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

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 2003;

bool vis[MXN][MXN];
vector<vector<int>> F;
int n, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y){
    vis[x][y] = 1;
    for(int d=0,xx,yy; d<4; d++) {
        xx = x+dx[d], yy = y+dy[d];
        if(0<=xx && xx<n && 0<=yy && yy<n && !vis[xx][yy] && F[xx][yy]==0)
            dfs(xx, yy);
    }
}

int biggest_stadium(int n, vector<vector<int>> F) {
    ::n = n;
    ::F = F;
    int cnt=0;
    for(int i=0; i<n; i++)
        for(int j : F[i])
            cnt += j;
    if(cnt==0) return n*n;
    if(cnt==1) {
        int x=-1, y=-1;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(F[i][j])
                    x=i, y=j;
        return n*n - min(x+1, n-x)*min(y+1, n-y);
    }
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(F[i][j]==0)
                dfs(i, j);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(F[i][j]==0 && !vis[i][j])
                return 0;
    int lstl=-1, lstr=-1;   
    bool p1=1;
    vector<pii> vec;
    for(int i=0; i<n; i++) {
        int l=-1, r=-1;
        for(int j=0; j<n; j++)
            if(F[i][j]==0) {
                if(l==-1) l=j;
                r = j;
            }
        if(l!=-1) {
            vec.push_back({l, -r});
            for(int j=l; j<=r; j++)
                if(F[i][j]==1)
                    return 0;
            if(lstl==-1);
            else if(p1) {
                if(l<=lstl && lstr<=r);
                else if(lstl<=l && r<=lstr) p1=0;
                else return 0;
            }
            else if(lstl<=l && r<=lstr);
            else return 0;
            lstl = l;
            lstr = r;
        }
    }
    sort(vec.begin(), vec.end());
    for(int i=0; i+1<vec.size(); i++)
        if(vec[i].Y>vec[i+1].Y)
            return 0;
    return n*n-cnt;
}

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