Submission #1209778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209778		PagodePaiva	Soccer Stadium (IOI23_soccer)	C++20	3.50 / 100	200 ms	31916 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 2010;
int linha_l[N], linha_r[N], coluna_l[N], coluna_r[N];
int linha_total[N], coluna_total[N];
int soma_linha[N], soma_coluna[N];
int pref_linha[N], pref_coluna[N];

int intercessao(int l1, int r1, int l2, int r2){
    ////cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << '\n';
    if(l1 > l2 or (l1 == l2 and r2 > r1)){
        swap(l1, l2);
        swap(r1, r2);
    }
    if(l1 > r2 or l2 > r1)
        return 0;
    if(l1 <= l2 and r2 <= r1){
        return pref_linha[r2] - (l2 > 0 ? pref_linha[l2-1] : 0);
    }
    return pref_linha[r2] - (l1 > 0 ? pref_linha[l1-1] : 0);
}

int intercessao2(int l1, int r1, int l2, int r2){
    if(l1 > l2 or (l1 == l2 and r2 > r1)){
        swap(l1, l2);
        swap(r1, r2);
    }
    if(l1 > r2 or l2 > r1)
        return 0;
    if(l1 <= l2 and r2 <= r1){
        return pref_coluna[r2] - (l2 > 0 ? pref_coluna[l2-1] : 0);
        
    }
    return pref_coluna[r2] - (l1 > 0 ? pref_coluna[l1-1] : 0);
}

int biggest_stadium(int n, vector<vector<int>> m){
    int tot = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            soma_linha[i] += (1-m[i][j]);
            soma_coluna[j] += (1-m[i][j]);
        }
    }
    pref_linha[0] = soma_linha[0];
    pref_coluna[0] = soma_coluna[0];
    for(int i = 1;i < n;i++){
        pref_linha[i] = pref_linha[i-1] + soma_linha[i];
        pref_coluna[i] = pref_coluna[i-1] + soma_coluna[i];
    }
    for(int i = 0;i < n;i++){
        int aux = 0;
        for(int j = 0;j < n;j++){
            if(m[i][j] == 0){
                tot++;
            }
            if(m[i][j] == 0 and aux == 0){
                aux = 1;
            }
            if(m[i][j] == 1 and aux == 1){
                aux = 2;
            }
            if(m[i][j] == 0 and aux == 2){
                return 0;
            }
        }
    }
    for(int j = 0;j < n;j++){
        int aux = 0;
        for(int i = 0;i < n;i++){
            if(m[i][j] == 0 and aux == 0){
                aux = 1;
            }
            if(m[i][j] == 1 and aux == 1){
                aux = 2;
            }
            if(m[i][j] == 0 and aux == 2){
                return 0;
            }
        }
    }
    for(int i = 0;i < n;i++){
        linha_l[i] = n+1, linha_r[i] = -1;
        for(int j = 0;j < n;j++){
            if(m[i][j] == 0){
                linha_l[i] = min(linha_l[i], j);
                linha_r[i] = max(linha_r[i], j);
            }
        }
        ////////cout << linha_l[i] << ' ' << linha_r[i] << '\n';
    }
    for(int j = 0;j < n; j++){
        coluna_l[j] = n+1, coluna_r[j] = -1;
        for(int i = 0;i < n;i++){
            if(m[i][j] == 0){
                coluna_l[j] = min(coluna_l[j], i);
                coluna_r[j] = max(coluna_r[j], i);
            }
        }
        ////////cout << coluna_l[j] << ' ' << coluna_r[j] << '\n';
    }
    ////////cout << tot << '\n';
    for(int i = 0;i < n;i++){
        int calc = 0;
        for(int j = 0;j < n;j++){
            if(m[i][j] == 0){
                calc += coluna_r[j] - coluna_l[j]+1;
            }
        }
        linha_total[i] = calc;
    }
    for(int j = 0;j < n;j++){
        int calc = 0;
        for(int i = 0;i < n;i++){
            if(m[i][j] == 0){
                calc += linha_r[i] - linha_l[i]+1;
            }
        }
        coluna_total[j] = calc;
    }
    for(int i = 0;i < n;i++){
        int l1 = linha_l[i], r1 = linha_r[i];
        if(l1 > r1)
            continue;
        int small_coluna = l1;
        for(int j = l1;j <= r1;j++){
            if(coluna_l[j] < coluna_l[small_coluna])
                small_coluna = j;
        }
        int big_coluna = l1;
        for(int j = l1;j <= r1;j++){
            if(coluna_r[j] > coluna_r[small_coluna])
                big_coluna = j;
        }
        l1 = small_coluna;
        r1 = big_coluna;
        ////cout << l1 << ' ' << r1 << '\n';
        ////cout << coluna_total[l1] << ' ' << coluna_total[r1] << '\n';
        int ans = coluna_total[l1] + coluna_total[r1];
        ans -= intercessao(coluna_l[l1], coluna_r[l1], coluna_l[r1], coluna_r[r1]);
        ////cout << ans << '\n';
        if(ans != tot){
            ////cout << 1 << ' ';
            ////cout << i << '\n';
            return 0;
        }
    }
    for(int j = 0;j < n;j++){
        int l1 = coluna_l[j], r1 = coluna_r[j];
        if(l1 > r1)
            continue;
        int small_coluna = l1;
        for(int i = l1;i <= r1;i++){
            if(linha_l[i] < linha_l[small_coluna])
                small_coluna = i;
        }
        int big_coluna = l1;
        for(int i = l1;i <= r1;i++){
            if(linha_r[i] > linha_r[small_coluna])
                big_coluna = i;
        }
        l1 = small_coluna;
        r1 = big_coluna;
        int ans = linha_total[l1] + linha_total[r1];
        //////cout << linha_total[l1] << ' ' << linha_total[r1] << '\n';
        ans -= intercessao2(linha_l[l1], linha_r[l1], linha_l[r1], linha_r[r1]);
        //////cout << ans << '\n';
        if(ans != tot){
            //cout << 2 << ' ';
            //cout << j << '\n';
            return 0;
        }
    }
    return tot;
}

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