oj.uz

Submission #1078860

# Submission time Handle Problem Language Result Execution time Memory
1078860 2024-08-28T07:18:14 Z PoPularPlusPlus Soccer Stadium (IOI23_soccer) C++17
0 / 100
 1 ms 432 KB 
#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(f[i][j] > mn_col[i] && f[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] == 0)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] == 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 / 0.0

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

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 8.0

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

Subtask #3
0.0 / 22.0

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

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 16.0

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

Subtask #6
0.0 / 30.0

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