Submission #839952

#	Time	Username	Problem	Language	Result	Execution time	Memory
839952		jonathanirvings	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	250 ms	31820 KiB

soccer

#include "soccer.h"

#include <bits/stdc++.h>
using namespace std;

bool inside(pair<int, int> a, pair<int, int> b) {
    return b.first <= a.first && a.second <= b.second;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    pair<int, int> inv = make_pair(-1, -1);
    vector<pair<int, int>> border(N, inv);
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (F[i][j] == 0) {
                ++ans;
                if (j == 0 || F[i][j - 1] == 1) {
                    if (border[i] != inv) {
                        return 0;
                    }
                    border[i].first = j;
                }
                border[i].second = j;
            }
        }
    }
    int mx = 0;
    for (int i = 0; i < N; ++i) {
        if (border[i] != inv && border[i].second - border[i].first
                             >= border[mx].second - border[mx].first) {
            mx = i;
        }
    }
    int l = mx - 1;
    int r = mx + 1;
    pair<int, int> now = border[mx];
    while ((l >= 0 && border[l] != inv) || (r < N && border[r] != inv)) {
        if (l < 0 || border[l] == inv) {
            if (!inside(border[r], now)) {
                return 0;
            }
            now = border[r];
            ++r;
        } else if (r >= N || border[r] == inv) {
            if (!inside(border[l], now)) {
                return 0;
            }
            now = border[l];
            --l;
        } else {
            if (border[r].second - border[r].first >= border[l].second - border[l].first) {
                if (!inside(border[r], now)) {
                    return 0;
                }
                now = border[r];
                ++r;
            } else {
                if (!inside(border[l], now)) {
                    return 0;
                }
                now = border[l];
                --l;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        if (i < l || i > r) {
            if (border[i] != inv) {
                return 0;
            }
        }
    }
    return ans;
}

• 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