oj.uz

Submission #916361

# Submission time Handle Problem Language Result Execution time Memory
916361 2024-01-25T18:20:32 Z chirathnirodha Soccer Stadium (IOI23_soccer) C++17
8 / 100
 273 ms 31764 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;}
    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 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
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 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 17 ms 2396 KB ok
9 Correct 273 ms 31764 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 0 ms 348 KB partial
4 Partially correct 0 ms 428 KB partial
5 Correct 1 ms 348 KB ok
6 Partially correct 1 ms 348 KB partial
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Partially correct 0 ms 348 KB partial
12 Partially correct 0 ms 348 KB partial
13 Correct 0 ms 348 KB ok

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 0 ms 348 KB partial
5 Partially correct 0 ms 428 KB partial
6 Correct 1 ms 348 KB ok
7 Partially correct 1 ms 348 KB partial
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Partially correct 0 ms 348 KB partial
13 Partially correct 0 ms 348 KB partial
14 Correct 0 ms 348 KB ok
15 Partially correct 0 ms 348 KB partial
16 Partially correct 0 ms 348 KB partial
17 Partially correct 0 ms 348 KB partial
18 Partially correct 1 ms 344 KB partial
19 Partially correct 1 ms 344 KB partial
20 Correct 1 ms 348 KB ok
21 Correct 1 ms 440 KB ok
22 Partially correct 1 ms 348 KB partial
23 Incorrect 1 ms 344 KB wrong
24 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 348 KB partial
7 Partially correct 0 ms 428 KB partial
8 Correct 1 ms 348 KB ok
9 Partially correct 1 ms 348 KB partial
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Partially correct 0 ms 348 KB partial
15 Partially correct 0 ms 348 KB partial
16 Correct 0 ms 348 KB ok
17 Partially correct 0 ms 348 KB partial
18 Partially correct 0 ms 348 KB partial
19 Partially correct 0 ms 348 KB partial
20 Partially correct 1 ms 344 KB partial
21 Partially correct 1 ms 344 KB partial
22 Correct 1 ms 348 KB ok
23 Correct 1 ms 440 KB ok
24 Partially correct 1 ms 348 KB partial
25 Incorrect 1 ms 344 KB wrong
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 348 KB partial
7 Partially correct 0 ms 428 KB partial
8 Correct 1 ms 348 KB ok
9 Partially correct 1 ms 348 KB partial
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Partially correct 0 ms 348 KB partial
15 Partially correct 0 ms 348 KB partial
16 Correct 0 ms 348 KB ok
17 Partially correct 0 ms 348 KB partial
18 Partially correct 0 ms 348 KB partial
19 Partially correct 0 ms 348 KB partial
20 Partially correct 1 ms 344 KB partial
21 Partially correct 1 ms 344 KB partial
22 Correct 1 ms 348 KB ok
23 Correct 1 ms 440 KB ok
24 Partially correct 1 ms 348 KB partial
25 Incorrect 1 ms 344 KB wrong
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 344 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 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 17 ms 2396 KB ok
10 Correct 273 ms 31764 KB ok
11 Partially correct 0 ms 348 KB partial
12 Partially correct 0 ms 428 KB partial
13 Correct 1 ms 348 KB ok
14 Partially correct 1 ms 348 KB partial
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 1 ms 348 KB ok
19 Partially correct 0 ms 348 KB partial
20 Partially correct 0 ms 348 KB partial
21 Correct 0 ms 348 KB ok
22 Partially correct 0 ms 348 KB partial
23 Partially correct 0 ms 348 KB partial
24 Partially correct 0 ms 348 KB partial
25 Partially correct 1 ms 344 KB partial
26 Partially correct 1 ms 344 KB partial
27 Correct 1 ms 348 KB ok
28 Correct 1 ms 440 KB ok
29 Partially correct 1 ms 348 KB partial
30 Incorrect 1 ms 344 KB wrong
31 Halted 0 ms 0 KB -