oj.uz

Submission #564466

# Submission time Handle Problem Language Result Execution time Memory
564466 2022-05-19T09:25:33 Z birthdaycake Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 89 ms 13864 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[2001][2001],vs[2001][2001],w[2001][2001];


int x[] = {-1,-1,-1,0,1,1,1,0}, y[] = {-1,0,1,1,1,0,-1,-1};
vector<pair<int,int>>p,nxt;
vector<int>ans;
int n;



bool cmp(int* a, int *b){
    return *a < *b;
}


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 = 0; 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]){
        //cout << a << ' ' << b << endl;
        nxt.push_back({a,b});
        ans.push_back(w[a][b]);
        return;
    }
    for(int k = 0; k < 8; k++){
        int aa = a + x[k], bb = b + y[k];
        if(aa < 0 || bb < 0 || aa >= n || bb >= n || !grid[aa][bb] || vs[aa][bb]) continue;
        dfs(aa,bb);
    }
    
}
signed main(){
    boost;
    
    
    
    int t; cin >> n >> t;
    vector<int*>d;
    for(int i = 0; i < n; i++){
        int x,y;
        cin >> x >> y;
        p.push_back({x,y});
        d.push_back(&p[i].first);
        d.push_back(&p[i].second);
    }
    if(!check()){
        cout << "NO";
        return 0;
    }
    sort(d.begin(), d.end(),cmp);
    int cur = -1, prev = 0;
    for(auto s:d){
        if(*s != prev) cur++;
        prev = *s;
        *s = cur;
    }
    for(int i = 0; i < n; i++){
        grid[p[i].first][p[i].second] = 1;
        w[p[i].first][p[i].second] = i;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i == 0 || j == 0 || i == n - 1|| j == n - 1) {
                if(!vs[i][j]) dfs(i,j);
            }
        }
    }
    //cout << nxt.size() << endl;
    while(!nxt.empty()){
        vector<pair<int,int>>nw = nxt;
        nxt.clear();
        for(int i = 0; i < nw.size(); i++){
            int a = nw[i].first, b = nw[i].second;
            for(int k = 0; k < 8; k++){
                int aa = a + x[k], bb = b + y[k];
                //cout << aa << ' ' << bb << endl;
                if(aa < 0 || bb < 0 || aa >= n || bb >= n || vs[aa][bb]) continue;
                //cout << aa << ' ' << bb << endl;
                //cout << vs[aa][bb] << endl;
                dfs(aa,bb);
            }
        }
        //cout << endl;
    }
    cout << "YES" << endl;
    for(int i = 0; i < n; i++){
        cout << ans[i] + 1 << endl;
    }
    
    return 0;
}

Compilation message

skyscrapers.cpp: In function 'bool check()':
skyscrapers.cpp:34: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]
   34 |     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 = 0; i < nw.size(); i++){
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Contestant did not find solution
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Contestant did not find solution
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Contestant did not find solution
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB ans=NO N=1934
2 Correct 1 ms 468 KB ans=NO N=1965
3 Runtime error 6 ms 852 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Contestant did not find solution
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 9592 KB ans=NO N=66151
2 Correct 28 ms 6264 KB ans=NO N=64333
3 Runtime error 89 ms 13864 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB ans=NO N=1934
2 Correct 1 ms 468 KB ans=NO N=1965
3 Runtime error 6 ms 852 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -