oj.uz

Submission #939219

# Submission time Handle Problem Language Result Execution time Memory
939219 2024-03-06T06:58:41 Z WanWan Soccer Stadium (IOI23_soccer) C++17
0 / 100
 18 ms 5468 KB 
#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 ny=*upper_bound(row[i].begin(),row[i].end(),j);
                    int nx=*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 ny=*upper_bound(row[i].begin(),row[i].end(),j);
                    int nx=*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 ny=*prev(lower_bound(row[i].begin(),row[i].end(),j));
                    int nx=*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 ny=*prev(lower_bound(row[i].begin(),row[i].end(),j));
                    int nx=*prev(lower_bound(col[j].begin(),col[j].end(),i));
                    if(V[nx][ny] == 0)return 0;
                }
            }
        }
    }


    return cnt;
}

Compilation message

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 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 600 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 636 KB ok
6 Partially correct 1 ms 600 KB partial
7 Partially correct 2 ms 604 KB partial
8 Runtime error 18 ms 5468 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB ok
2 Correct 0 ms 604 KB ok
3 Partially correct 0 ms 604 KB partial
4 Partially correct 1 ms 856 KB partial
5 Partially correct 1 ms 604 KB partial
6 Incorrect 1 ms 604 KB wrong
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 600 KB partial
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 604 KB ok
4 Partially correct 0 ms 604 KB partial
5 Partially correct 1 ms 856 KB partial
6 Partially correct 1 ms 604 KB partial
7 Incorrect 1 ms 604 KB wrong
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 600 KB partial
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 1 ms 604 KB ok
6 Partially correct 0 ms 604 KB partial
7 Partially correct 1 ms 856 KB partial
8 Partially correct 1 ms 604 KB partial
9 Incorrect 1 ms 604 KB wrong
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 600 KB partial
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 1 ms 604 KB ok
6 Partially correct 0 ms 604 KB partial
7 Partially correct 1 ms 856 KB partial
8 Partially correct 1 ms 604 KB partial
9 Incorrect 1 ms 604 KB wrong
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 600 KB partial
2 Correct 1 ms 600 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 1 ms 604 KB ok
6 Correct 0 ms 636 KB ok
7 Partially correct 1 ms 600 KB partial
8 Partially correct 2 ms 604 KB partial
9 Runtime error 18 ms 5468 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -