Submission #1225396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225396		amine_aroua	Soccer Stadium (IOI23_soccer)	C++20	38.50 / 100	4547 ms	761472 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};
int gans = 0;
vector<pair<int ,int>> v;
vector<vector<int>> grid;
int MAXN = 0;
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 = (int)v.size() - 1;
    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(MAXN + 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 = MAXN ; i >= 1 ; i--)
    {
        for(auto r : l[i])
        {
            if(mxR > r)
            {
                return 0;
            }
        }
        for(auto r : l[i])
        {
            mxR = max(mxR , r);
        }
    }
    return 1;
}

vector<vector<pair<int, int>>> intervals;

void get_intervals(int N)
{
    for(int i = 1 ; i <= N ; i++)
    {
        for(int j = 1 ; j <= N ; )
        {
            int k = j;
            for( ; j <= N && grid[i][j] == grid[i][k]; j++);
            if(grid[i][k] == 0)
            {
                int lt = k , rt = j - 1;
                for(int h = lt ; h <= rt ; h++)
                {
                    for(int l = h ; l <= rt ; l++)
                    {
                        intervals[i].push_back({h , l});
                    }
                }
            }
        }
        sort(intervals[i].rbegin() , intervals[i].rend() , [](pair<int ,int> a , pair<int, int> b){return a.second-a.first < b.second-b.first;});
    }
}
int cur = 0;
void brute(int i)
{   
    if (1.0 * clock() / CLOCKS_PER_SEC >= 4.4)
        return ;
    if(i == MAXN + 1)
    {
        // cerr<<"cur : "<<cur<<'\n';
        // cerr<<(int)v.size()<<'\n';
        return ;
    }
    for(auto [l , r] : intervals[i])
    {
        if (1.0 * clock() / CLOCKS_PER_SEC >= 4.4)
            return ;
        // cerr<<i<<" "<<l<<" "<<r<<'\n'; 
        v.push_back({l , r});
        bool check = works();
        if(check)
        {
            cur+= r - l + 1;
            gans = max(gans , cur);
            brute(i + 1);
            cur-= (r - l + 1);
            v.pop_back();
        }
        else
            v.pop_back();
    }
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    MAXN = N;
    gans = 0;
    v.clear();
    grid.assign(N + 2 ,vector<int> (N + 2 , 1));
    intervals.assign(N + 1 , vector<pair<int ,int>>());
    for(int i= 1 ; i <= N ; i++)
    {
        for(int j = 1 ; j <= N ; j++)
        {
            grid[i][j] = F[i-1][j-1];
        }
    }

    get_intervals(N);
    for(int i = 1 ; i <= MAXN ; i++)
    {
        v.clear();
        cur = 0;
        v.push_back({-1 , -1});
        brute(i );
    }
    assert(gans >= 1);
    return gans;
}

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

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