oj.uz

Submission #564664

# Submission time Handle Problem Language Result Execution time Memory
564664 2022-05-19T12:46:32 Z birthdaycake Building Skyscrapers (CEOI19_skyscrapers) C++14
0 / 100
 534 ms 1048576 KB 
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 
 
 
int grid[5001][5001],vs[5001][5001],w[5001][5001];
 
 
int x[] = {-1,-1,-1,0,1,1,1,0}, y[] = {-1,0,1,1,1,0,-1,-1};
int xx[] = {0,0,1,-1}, yy[] = {1,-1,0,0};
vector<pair<int,int>>p;
vector<pair<int,int>>nxt;
vector<int>ans;
int n;
 
vector<int>fin[200001];
 
 
bool check(){
    vector<pair<int,int>>b;
    b.push_back({p[0].first,p[0].second});
    set<pair<int,int>>c,d;
    for(int i = 1; i < n; i++){
        d.insert({p[i].first,p[i].second});
    }
    int j = 0;
    while(j < b.size()){
        for(int k = 0; k < 8; k++){
            int nx = b[j].first + x[k], ny = b[j].second + y[k];
            if(d.count({nx,ny})){
                d.erase({nx,ny});
                b.push_back({nx,ny});
            }
        }
        j++;
    }
    return d.empty();
}
 
 


void dfs(int a, int b){
    vs[a][b] = 1;
    if(grid[a][b]){
        nxt.push_back({a,b});
        return;
    }
    for(int k = 0; k < 4; k++){
        int aa = a + xx[k], bb = b + yy[k];
        if(aa < 0 || bb < 0 || aa >= 2 * n || bb >= 2 * n || vs[aa][bb]) continue;
        dfs(aa,bb);
    }
}
signed main(){
    boost;
    
    
    
    int t, cnt = 0; cin >> n >> t;
    vector<int*>d;
    set<int>tt; map<int,int>bb;
    for(int i = 0; i < n; i++){
        int x,y;
        cin >> x >> y;
        p.push_back({x,y});
        tt.insert(x); tt.insert(y);
    }
    if(!check()){
        cout << "NO";
        return 0;
    }
    for(auto s:tt){
        bb[s] = cnt++;
    }
    for(int i = 0; i < n; i++){
        p[i].first = bb[p[i].first];
        p[i].second = bb[p[i].second];
        grid[p[i].first][p[i].second] = 1;
        w[p[i].first][p[i].second] = i;
    }
    for(int i = 0; i < 2 * n; i++){
        for(int j = 0; j < 2 * n; j++){
            if(i == 0 || j == 0 || i == 2 * n - 1 || j == 2 * n - 1){
                if(!vs[i][j]){
                    dfs(i,j);
                }
            }
        }
    }
    int cc = 0;
    while(nxt.size()){
        vector<pair<int,int>>b;
        set<pair<int,int>>s;
        set<int>u;
        b.push_back({nxt[0].first,nxt[0].second});
        u.insert(w[nxt[0].first][nxt[0].second]);
        for(int i = 1; i < nxt.size(); i++){
            s.insert({nxt[i].first,nxt[i].second});
            
        }
        int j = 0;
        while(j < b.size()){
            for(int k = 0; k < 8; k++){
                int nx = b[j].first + x[k], ny = b[j].second + y[k];
                if(s.find({nx,ny}) != s.end()){
                    s.erase({nx,ny});
                    b.push_back({nx,ny});
                    u.insert(w[nx][ny]);
                }
            }
            j++;
        }
        nxt.clear();
        int f = -1;
        for(int i = 0; i < b.size(); i++){
            for(int k = 0; k < 4; k++){
                int aa = b[i].first + xx[k], bb = b[i].second + yy[k];
                if(aa < 0 || bb < 0 || aa >= 2 * n || bb >= 2 * n || vs[aa][bb]) continue;
                if(grid[aa][bb]) {
                    if(u.count(w[b[i].first][b[i].second])){
                        fin[cc].push_back(w[b[i].first][b[i].second]);
                        u.erase(w[b[i].first][b[i].second]);
                    }
                    dfs(aa,bb);
                }
            }
            if(f != -1) break;
        }
        for(auto s:u){
            fin[cc].push_back(s);
        }
        for(int i = 0; i < b.size(); i++){
            for(int k = 0; k < 4; k++){
                int aa = b[i].first + xx[k], bb = b[i].second + yy[k];
                if(aa < 0 || bb < 0 || aa >= 2 * n || bb >= 2 * n || vs[aa][bb]) continue;
                dfs(aa,bb);
            }
        }
        cc++;
    }
    cout << "YES" << endl;
    for(int i = cc - 1; i >= 0; i--){
        for(int j = 0; j < fin[i].size(); j++){
            cout << fin[i][j] + 1 << endl;
        }
    }
    
    
    
    return 0;
}

Compilation message

skyscrapers.cpp: In function 'bool check()':
skyscrapers.cpp:32:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(j < b.size()){
      |           ~~^~~~~~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:103:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int i = 1; i < nxt.size(); i++){
      |                        ~~^~~~~~~~~~~~
skyscrapers.cpp:108:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         while(j < b.size()){
      |               ~~^~~~~~~~~~
skyscrapers.cpp:121:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int i = 0; i < b.size(); i++){
      |                        ~~^~~~~~~~~~
skyscrapers.cpp:138:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for(int i = 0; i < b.size(); i++){
      |                        ~~^~~~~~~~~~
skyscrapers.cpp:149:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int j = 0; j < fin[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB ans=YES N=1
2 Correct 3 ms 5076 KB ans=YES N=4
3 Correct 3 ms 4948 KB ans=NO N=4
4 Correct 3 ms 5076 KB ans=YES N=5
5 Correct 3 ms 5076 KB ans=YES N=9
6 Correct 3 ms 5076 KB ans=YES N=5
7 Correct 2 ms 4948 KB ans=NO N=9
8 Correct 3 ms 4948 KB ans=NO N=10
9 Incorrect 3 ms 5076 KB Full cells must be connected
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB ans=YES N=1
2 Correct 3 ms 5076 KB ans=YES N=4
3 Correct 3 ms 4948 KB ans=NO N=4
4 Correct 3 ms 5076 KB ans=YES N=5
5 Correct 3 ms 5076 KB ans=YES N=9
6 Correct 3 ms 5076 KB ans=YES N=5
7 Correct 2 ms 4948 KB ans=NO N=9
8 Correct 3 ms 4948 KB ans=NO N=10
9 Incorrect 3 ms 5076 KB Full cells must be connected
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB ans=YES N=1
2 Correct 3 ms 5076 KB ans=YES N=4
3 Correct 3 ms 4948 KB ans=NO N=4
4 Correct 3 ms 5076 KB ans=YES N=5
5 Correct 3 ms 5076 KB ans=YES N=9
6 Correct 3 ms 5076 KB ans=YES N=5
7 Correct 2 ms 4948 KB ans=NO N=9
8 Correct 3 ms 4948 KB ans=NO N=10
9 Incorrect 3 ms 5076 KB Full cells must be connected
10 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB ans=NO N=1934
2 Correct 3 ms 5076 KB ans=NO N=1965
3 Runtime error 485 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB ans=YES N=1
2 Correct 3 ms 5076 KB ans=YES N=4
3 Correct 3 ms 4948 KB ans=NO N=4
4 Correct 3 ms 5076 KB ans=YES N=5
5 Correct 3 ms 5076 KB ans=YES N=9
6 Correct 3 ms 5076 KB ans=YES N=5
7 Correct 2 ms 4948 KB ans=NO N=9
8 Correct 3 ms 4948 KB ans=NO N=10
9 Incorrect 3 ms 5076 KB Full cells must be connected
10 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 13272 KB ans=NO N=66151
2 Correct 37 ms 10016 KB ans=NO N=64333
3 Runtime error 534 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB ans=NO N=1934
2 Correct 3 ms 5076 KB ans=NO N=1965
3 Runtime error 485 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -