Submission #840853

#	Time	Username	Problem	Language	Result	Execution time	Memory
840853		Lucpp	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	387 ms	31820 KiB

soccer

#include <bits/stdc++.h>
#include "soccer.h"
using namespace std;
using pii = pair<int, int>;
constexpr pii id = {-1, -1};

bool inside(pii a, pii b){
    if(a.first == -1) return true;
    if(b.first == -1) return false;
    return b.first <= a.first && a.second <= b.second;
}

int biggest_stadium(int N, vector<vector<int>> F){
    vector<pii> v(N);
    int flag = 0;
    int start = 0;
    for(int i = 0; i < N; i++){
        int l = -1, r = -1;
        for(int j = 0; j < N; j++){
            if(F[i][j] == 0){
                if(l == -1) l = j;
                r = j;
            }
        }
        for(int j = l; j < r+1; j++){
            if(F[i][j]) return 0;
        }
        v[i] = {l, r};
        if(flag == 0 && l != -1) flag = 1;
        if(flag == 1 && l == -1) flag = 2;
        if(flag == 2 && l != -1) return 0;
        if(inside(v[start], v[i])) start = i;
    }
    int lo = start, hi = start;
    while(true){
        pii le = (lo > 0 ? v[lo-1] : id);
        pii ri = (hi < N-1 ? v[hi+1] : id);
        if(le == id && ri == id) break;
        if(!inside(le, v[lo]) || !inside(le, v[hi]) || !inside(ri, v[lo]) || !inside(ri, v[hi])) return 0;
        if(inside(le, ri)) hi++;
        else if(inside(ri, le)) lo--;
        else return 0;
    }
    int cnt = 0;
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) cnt += F[i][j]^1;
    return cnt;
}

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