Submission #1225337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225337		amine_aroua	Soccer Stadium (IOI23_soccer)	C++20	25 / 100	234 ms	47652 KiB

soccer

#include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
int ret = 0;
int xx [] = {-1 , 1 , 0 , 0};
int yy[] = {0 , 0 , -1 , 1};
vector<vector<int>> grid;
int get_nest(pair<int ,int> a , pair<int ,int> b)
{
    if(a.first == b.first && a.second == b.second)
        return 2;
    if(a.first <= b.first && b.second <= a.second)
        return 0;
    swap(a , b);
    if(a.first <= b.first && b.second <= a.second)
        return 1;
    return -1;
}

bool works(int N)
{
    vector<pair<int , int>> v(N + 2 , {-1 , -1});
    for(int i = 1 ; i <= N ; i++)
    {
        int ans = 0;
        for(int j = 1 ;j <= N+  1 ; j++)
        {
            ans+=(grid[i][j] != grid[i][j - 1]);
        }
        if(ans != 2 && ans!= 0)
        {
            return 0;
        }
        int fr = -1;
        int lst = -1;
        for(int j = 1 ; j <= N ; j++)
        {
            if(grid[i][j] == 0)
            {
                if(fr== -1)
                    fr = j;
                lst = j;
            }
        }
        v[i] = {fr , lst};
    }
    int cnt = 0;
    for(int i = 1 ; i <= N + 1 ; i++)
    {
        cnt+=(v[i - 1].first == -1 && v[i].first != -1) + (v[i - 1].first != -1 && v[i].first == -1);
    }
    // cout<<cnt<<'\n';
    if(cnt != 2)
        return 0;
    int lst0 = 0;
    vector<int> type(N + 1);
    for(int i = 2 ; i <= N ; i++)
    {
        if(v[i].first == -1 || v[i - 1].first == -1)
        {
            type[i] = 2;
            continue;
        }
        if(v[i].first == v[i - 1].first && v[i].second == v[i - 1].second)
        {
            type[i] = 2;
            continue;
        }
        type[i] = get_nest(v[i] , v[i - 1]);
        if(type[i] == -1)
        {
            return 0;
        }
        if(type[i] == 0)
            lst0 = i;
    }
    if(lst0 == 0)
    {
        return 1;
    }
    int nb1 = count(type.begin() + 2 , type.begin() + lst0+1 , 1);
    if(nb1)
        return 0;
    vector<vector<int>>l(N + 1);
    for(int i = 1 ; i <= N ; i++)
    {
        if(v[i].first != -1)
        {
            l[v[i].first].push_back(v[i].second);
        }
    }
    int mxR = 0;
    for(int i = N ; i >= 1 ; i--)
    {
        for(auto r : l[i])
        {
            if(mxR > r)
            {
                return 0;
            }
        }
        for(auto r : l[i])
        {
            mxR = max(mxR , r);
        }
    }
    return 1;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    ret = 0;
    grid.assign(N + 2 ,vector<int> (N + 2 , 1));
    for(int i= 1 ; i <= N ; i++)
    {
        for(int j = 1 ; j <= N ; j++)
        {
            grid[i][j] = F[i-1][j-1];
            ret+=(F[i - 1][j - 1]^1);
        }
    }
    bool check = works(N);
    
    // cout<<check<<'\n';
    if(check)
    {
        assert(ret != 0);
        return ret;
    }
    return 0;
}

/*
  --
 ----
 ----
------
------
 ----
*/

• 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