oj.uz

Submission #916625

# Submission time Handle Problem Language Result Execution time Memory
916625 2024-01-26T07:29:36 Z chirathnirodha Soccer Stadium (IOI23_soccer) C++17
6 / 100
 254 ms 39568 KB 
#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=-1;
        //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++){
                    if(arr[c][d]==1)continue;
                    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;
    }
    if(v[cur]==-1){
        v[cur]=0;
        comput(v,cur+1,siz+1);
        v[cur]=1;
        comput(v,cur+1,siz);
        v[cur]=-1;
    }
    else comput(v,cur+1,siz);
    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 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 16 ms 2828 KB ok
9 Correct 254 ms 39568 KB ok

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 600 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Incorrect 1 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 600 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Incorrect 1 ms 348 KB wrong
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 600 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Incorrect 1 ms 348 KB wrong
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 600 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Incorrect 1 ms 348 KB wrong
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 16 ms 2828 KB ok
10 Correct 254 ms 39568 KB ok
11 Correct 0 ms 600 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Incorrect 1 ms 348 KB wrong
15 Halted 0 ms 0 KB -