Submission #980240

#	Time	Username	Problem	Language	Result	Execution time	Memory
980240		vjudge1	Soccer Stadium (IOI23_soccer)	C++17	35.50 / 100	347 ms	40016 KiB

soccer

    #include "soccer.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) cout<<#x<<": "<<x<<endl;
int biggest_stadium(int N, vector<vector<int>> F)
{
    if(N>3){
int numoftree=0;
 for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j){
        if(F[i][j]==1){
            numoftree++;
        }
    }
 }
if(numoftree<=1){
 for(int i=0; i<N; ++i){
    for(int j=0; j<N; ++j){
        if(F[i][j]==1){
            int ans=min((i+1)*(j+1), (N-i)*(j+1));
            ans=min(ans, (i+1)*(N-j));
            ans=min(ans, (N-i)*(N-j));
            ans=N*N-ans;
            return ans;
        }
    }
 }
 return N*N;
    }
    else{

        bool jala=true;
        for(int i=0; i<N && jala; ++i){
            int notree=0;
            int tree=0;
            for(int j=0; j<N && jala; ++j){
                if(F[i][j]==1){
                  if(notree>0) tree++;
                }
                else{
                    if(notree>0 && tree>0){
                        jala=false;
                    }
                    notree++;
                }
            }
        }
         for(int i=0; i<N && jala; ++i){
            int notree=0;
            int tree=0;
            for(int j=0; j<N && jala; ++j){
                if(F[j][i]==1){
                   if(notree>0) tree++;
                }
                else{
                    if(notree>0 && tree>0){
                        jala=false;
                    }
                    notree++;
                }
            }
        }

        queue<pair<int,int>> q;
        for(int i=0; i<N && q.empty(); ++i){
            for(int j=0; j<N && q.empty(); ++j){
                if(F[i][j]==0){
                    q.push({i,j});
                }
            }
        }
        while(!q.empty()){
            int a=q.front().first;
            int b=q.front().second;
            q.pop();
            if(F[a][b]==2) continue;
            F[a][b]=2;
            if(b-1>=0 && F[a][b-1]==0){
                F[a][b-1]=-1;
                q.push({a, b-1});
            }
            if(a-1>=0 && F[a-1][b]==0){
                F[a-1][b]=-1;
                q.push({a-1, b});
            }
            if(b+1<N && F[a][b+1]==0){
                F[a][b+1]=-1;
                q.push({a, b+1});
            }
            if(a+1<N && F[a+1][b]==0){
                F[a+1][b]=-1;
                q.push({a+1, b});
            }
            
        }
        for(int i=0; i<N && jala; ++i){
            for(int j=0; j<N && jala; ++j){
                if(F[i][j]==0){
                    jala=false;
                }
            }
        }

        if(jala){

            vector<pair<int,int>> ranges;
            for(int i=0; i<N; ++i){
                int l=-1;
                int r=-1;
                for(int j=0; j<N; ++j){
                    if(F[i][j]==2){
                        if(l==-1){
                            l=j;
                        }
                        r=j;
                    }
                }
                if(l!=-1){
                    ranges.pb({l,r});
                }
            }
            for(int i=0; i<ranges.size() && jala; ++i){
                for(int j=i+1; j<ranges.size() && jala; ++j){
                    if(ranges[i].first >= ranges[j].first && ranges[i].first <=ranges[j].second){
                        //uwu
                    }
                    else{
                        if(ranges[i].first <=ranges[j].first && ranges[j].second <= ranges[i].second){
                            //uwu
                        }
                        else{
                            jala=false;
                        }
                    }
                    if(ranges[i].second >= ranges[j].first && ranges[i].second <=ranges[j].second){
                        //uwu
                    }
                    else{
                        if(ranges[i].first <=ranges[j].first && ranges[j].second <= ranges[i].second){
                            //uwu
                        }
                        else{
                            jala=false;
                        }
                    }
                }
            }
            if(jala){
            return N*N-numoftree;
            }
            return N*N-numoftree+1;
        }
        else{
            return N*N-numoftree+1;
        }
    }
    }
    int ans=0;
    int ayuda=N*N;
    int mevoyamorir=pow(2, ayuda);
    
    for(int mask=0;mask < mevoyamorir; ++mask){
        vector<vector<int>> grid (N, vector<int> (N, 0));
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
                if(F[i][j]==1){
                    grid[i][j]=-1;
                }
            }
        }
        int aux=mask;
    	int col=0;
        int fil=0;
        vector<pair<int,int>> coord;
        while(aux>0){
            if(aux%2){
                if(grid[fil][col]==-1){
                    break;
                }
                grid[fil][col]=1;
                coord.pb({fil, col});
            }
            col++;
            if(col>=N){
                fil++;
                col=0;
            }
            aux/=2;
        }
        if(aux>0){
            continue;
        }
        bool posib=true;

        for(int i=0; i<coord.size(); ++i){
            for(int j=i+1; j<coord.size(); ++j){
                if(grid[coord[i].first][coord[j].second]==1 || grid[coord[j].first][coord[i].second]==1){
                    if(coord[i].first==coord[j].first){
                        int a=coord[i].second;
                        int b=coord[j].second;
                        if(a>b) swap(a,b);
                        for(int x=a; x<=b; ++x){
                            if(grid[coord[i].first][x]!=1){
                                posib=false;
                                break;
                            }
                        } 
                        if(!posib) break;
                    }
                    if(coord[i].second==coord[j].second){
                        int a=coord[i].first;
                        int b=coord[j].first;
                        if(a>b) swap(a,b);
                        for(int x=a; x<=b; ++x){
                            if(grid[x][coord[i].second]!=1){
                                posib=false;
                                break;
                            }
                        } 
                        if(!posib) break;
                    }
                }
                else{
                    posib=false;
                    break;
                }
            }
            if(!posib) break;
        }
        if(posib){

            ans=max(ans,(int) coord.size());
        }

    }
    return ans;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for(int i=0; i<ranges.size() && jala; ++i){
      |                          ~^~~~~~~~~~~~~~
soccer.cpp:124:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |                 for(int j=i+1; j<ranges.size() && jala; ++j){
      |                                ~^~~~~~~~~~~~~~
soccer.cpp:196:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         for(int i=0; i<coord.size(); ++i){
      |                      ~^~~~~~~~~~~~~
soccer.cpp:197:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |             for(int j=i+1; j<coord.size(); ++j){
      |                            ~^~~~~~~~~~~~~

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