Submission #839791

#	Time	Username	Problem	Language	Result	Execution time	Memory
839791		model_code	Soccer Stadium (IOI23_soccer)	C++17	25 / 100	366 ms	36900 KiB

soccer

// partially_correct/authors_subtaskA6.cpp

// ##################################
// ##                              ##
// ##   Solution for Subtask A6    ##
// ##         (25.00 pts)          ##
// ##                              ##
// ##################################

#include <iostream>
#include <vector>
#include <algorithm>

#include "soccer.h"

using namespace std;

int biggest_stadium(int N, vector<vector<int>> C)
{
    vector<int> l(N, N);
    vector<int> r(N, -1);
    vector<int> h(N, 0);

    // Condition 1: All rows are interval
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (C[i][j] == 1)
                continue;
            l[i] = min(l[i], j);
            r[i] = max(r[i], j);
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = l[i]; j <= r[i]; j++)
        {
            if (C[i][j] == 1)
                return -1; // Failed
        }
    }

    // Condition 2: All two ranges are "overlap"
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            bool flag = false;
            if (l[i] <= l[j] && r[j] <= r[i])
                flag = true;
            if (l[j] <= l[i] && r[i] <= r[j])
                flag = true;
            if (flag == false)
                return -1; // Failed
        }
    }

    // Condition 3: Histogram of empty cells is "mountain"
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (C[i][j] == 0)
                h[i] += 1;
        }
    }
    int Max_Value = -1, Max_Index = -1;
    for (int i = 0; i < N; i++)
    {
        if (Max_Value < h[i])
        {
            Max_Value = h[i];
            Max_Index = i;
        }
    }
    for (int i = Max_Index - 1; i >= 0; i--)
    {
        if (h[i] > h[i + 1])
            return -1; // Failed
    }
    for (int i = Max_Index + 1; i < N; i++)
    {
        if (h[i - 1] < h[i])
            return -1; // Failed
    }

    // Success: If entire empty cells are regular
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (C[i][j] == 0)
                cnt++;
        }
    }
    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