Submission #916360

#	Time	Username	Problem	Language	Result	Execution time	Memory
916360		chirathnirodha	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	254 ms	38888 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
#define I insert
typedef long long ll;

int n,ans;
bool valid(vector<int> v){
    bool arr[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(v[i*n+j])arr[i][j]=1;
            else arr[i][j]=0;
        }
    }
    int pos[n][n][4];
    for(int i=0;i<n;i++){
        int cur=-1;
        //left
        for(int j=0;j<n;j++){
            pos[i][j][0]=cur;
            if(arr[i][j])cur=j;
        }
        cur=n;
        //right
        for(int j=n-1;j>=0;j--){
            pos[i][j][1]=cur;
            if(arr[i][j])cur=j;
        }
        cur=0;
        //up
        for(int j=0;j<n;j++){
            pos[j][i][2]=cur;
            if(arr[j][i])cur=j;
        }
        cur=n;
        //down
        for(int j=n-1;j>=0;j--){
            pos[j][i][3]=cur;
            if(arr[j][i])cur=j;
        }
    }

    for(int a=0;a<n;a++){
        for(int b=0;b<n;b++){
            if(arr[a][b]==1)continue;
            for(int c=a;c<n;c++){
                for(int d=b;d<n;d++){
                    bool ok1=false,ok2=false;
                    if(pos[a][b][1]>d && pos[c][d][2]<a)ok1=true;
                    if(pos[a][b][3]>c && pos[c][d][0]<b)ok2=true;
                    if(!ok1 && !ok2)return false;
                }
            }
        }
    }
    return true;
}
void comput(vector<int> v,int cur,int siz){
    if(cur==n*n)if(valid(v)){ans=max(ans,siz);return;}
    for(int i=cur;i<n*n;i++){
        if(v[i]==-1){
            v[i]=0;
            comput(v,i+1,siz+1);
            v[i]=1;
            comput(v,i+1,siz);
            v[i]=-1;
        }   
    }
    return;
}
int biggest_stadium(int N, vector<vector<int>> F){
    n=N;
    ans=0;
    int trees=0;pair<int,int> tr;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(F[i][j]){trees++;tr={i,j};}
    if(trees==0)return n*n;
    if(trees==1){
        int x=tr.F,y=tr.S;
        int a=n*x+y*(n-x) , b=n*x+(n-x)*(n-y-1) , c=n*(n-x-1)+y*(x+1) , d=n*(n-x-1)+(x+1)*(n-y-1);
        return max(max(a,b),max(c,d));
    }
    vector<int> v;
	v.assign(n*n,-1);
    if(n<=3){
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(F[i][j])v[i*n+j]=1;
        comput(v,0,0);
        return ans;
    }
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
        if(F[i][j])v[i*n+j]=1;
        else v[i*n+j]=0;
    }
    if(valid(v))return n*n-trees;
    else return 0;
}

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