Submission #939212

#	Time	Username	Problem	Language	Result	Execution time	Memory
939212		WanWan	Soccer Stadium (IOI23_soccer)	C++17	7.50 / 100	18 ms	5468 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 2005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
vector<int> row[MAXN], col[MAXN];
vector<int> rowh[MAXN],colh[MAXN];
struct ufds_{
    int p[MAXN];
    ufds_(){
        iota(p,p+MAXN,0);
    }
    int find(int x){
        if(x==p[x])return x;
        else return p[x]=find(p[x]);
    }
    void merge(int x, int y){
        x=find(x);y=find(y);
        p[y]=x;
    }
}ufds;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int n;
int get(int x, int y){
    return x*n+y;
}
int biggest_stadium(int N, std::vector<std::vector<int>> V)
{
    n=N;
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j] == 0){
                ++cnt;
                for(int k=0;k<3;k++){
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(nx<0 || nx>=n ||ny<0 || ny>=n || V[nx][ny])continue;
                    ufds.merge(get(i,j),get(nx,ny));
                }
            }
        }
    }
    unordered_set<int>os;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j] == 0)os.insert(ufds.find(get(i,j)));
        }
    }
    if(os.size() > 1)return 0;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j])row[i].push_back(j);
            else rowh[i].push_back(j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j])col[j].push_back(i);
            else colh[j].push_back(i);
        }
    }
    for(int i=0;i<n;i++){
        if(rowh[i].empty())continue;
        int st=rowh[i][0];
        int en=rowh[i].back();
        if(en-st+1 != rowh[i].size()){
            return 0;
        }
    }
     for(int j=0;j<n;j++){
        if(colh[j].empty())continue;
        int st=colh[j][0];
        int en=colh[j].back();
        if(en-st+1 != colh[j].size()){
            return 0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(V[i][j] == 0){
                if(upper_bound(row[i].begin(),row[i].end(),j) != row[i].end() && upper_bound(col[j].begin(),col[j].end(),i) != col[j].end()){
                    int nx=*upper_bound(row[i].begin(),row[i].end(),j);
                    int ny=*upper_bound(col[j].begin(),col[j].end(),i);
                    if(V[nx][ny] == 0)return 0;
                }
                if(upper_bound(row[i].begin(),row[i].end(),j) != row[i].end() && lower_bound(col[j].begin(),col[j].end(),i) != col[j].begin()){
                    int nx=*upper_bound(row[i].begin(),row[i].end(),j);
                    int ny=*prev(lower_bound(col[j].begin(),col[j].end(),i));
                    if(V[nx][ny] == 0)return 0;
                }
                if(lower_bound(row[i].begin(),row[i].end(),j) != row[i].begin() && upper_bound(col[j].begin(),col[j].end(),i) != col[j].end()){
                    int nx=*prev(lower_bound(row[i].begin(),row[i].end(),j));
                    int ny=*upper_bound(col[j].begin(),col[j].end(),i);
                    if(V[nx][ny] == 0)return 0;
                }
                if(lower_bound(row[i].begin(),row[i].end(),j) != row[i].begin() && lower_bound(col[j].begin(),col[j].end(),i) != col[j].begin()){
                    int nx=*prev(lower_bound(row[i].begin(),row[i].end(),j));
                    int ny=*prev(lower_bound(col[j].begin(),col[j].end(),i));
                    if(V[nx][ny] == 0)return 0;
                }
            }
        }
    }


    return cnt;
}

Compilation message (stderr)

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if(en-st+1 != rowh[i].size()){
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~
soccer.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         if(en-st+1 != colh[j].size()){
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~

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