oj.uz

Submission #564564

# Submission time Handle Problem Language Result Execution time Memory
564564 2022-05-19T11:13:11 Z birthdaycake Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 3500 ms 833560 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[5005][5005],vs[5005][5005];
 
 
int xxx[] = {-1,-1,-1,0,1,1,1,0}, yyy[] = {-1,0,1,1,1,0,-1,-1};
int x[] = {0,0,-1,1}, y[] = {1,-1,0,0};
vector<pair<int,int>>p,nxt;
int n, f, ans;
 
 
 
 
 
bool check(){
    vector<pair<int,int>>b;
    b.push_back({p[0].first,p[0].second});
    set<pair<int,int>>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 + xxx[k], ny = b[j].second + yyy[k];
            if(d.find({nx,ny}) != d.end()){
                d.erase({nx,ny});
                b.push_back({nx,ny});
            }
        }
        j++;
    }
    return d.empty();
}
 
bool cmp(int* a, int *b){
    return *a < *b;
}
 
 
void dfs(int a, int b){
    vs[a][b] = 1;
    if(a == 0 || b == 0 || a == 2 * n - 1 || b == 2 * n - 1){
        f = 1;
        return;
    }
    for(int k = 0; k < 4; k++){
        int aa = a + x[k], bb = b + y[k];
        if(f) return;
        if(aa < 0 || bb < 0 || aa >= 2 * n || bb >= 2 * n || vs[aa][bb] || grid[aa][bb])  continue;
        dfs(aa,bb);
    }
}
 
signed main(){
    boost;
    
    
    
    int t; cin >> n >> t;
    vector<int*>d;
    vector<pair<int,pair<int,int>>>c;
    set<int>tt; map<int,int>b;
    for(int i = 0; i < n; i++){
        int xx,yy; cin >> xx >> yy;
        p.push_back({xx,yy});
        tt.insert(xx);
        tt.insert(yy);
    }
    if(!check()){
        cout << "NO";
        return 0;
    }
    int cnt = 0;
    for(auto s:tt){
        b[s] = cnt++;
    }
    for(int i = 0; i < n; i++){
        p[i].first = b[p[i].first];
        p[i].second = b[p[i].second];
        c.push_back({p[i].first,{p[i].second,i}});
    }
    sort(c.begin(), c.end());
    
    
    
    do{
        int x = c[0].first, y = c[0].second.first, no = 0;
        grid[x][y] = 1;
        for(int i = 1; i < n; i++){
            int ok = 0;
            for(int j  =0; j < i; j++){
                if(abs(c[i].first - c[j].first) <= 1 && abs(y - c[j].second.first) <= 1){
                    ok = 1;
                    break;
                }
            }
            if(!ok){
                no = 1;
                break;
            }
            dfs(c[i].first,c[i].second.first);
            for(int k = 0; k < 2 * n ;k++){
                for(int j = 0; j < 2 * n; j++)  vs[k][j] = 0;
            }
            if(!f) no = 1;
            f = 0;
            if(no) break;
            x = c[i].first; y = c[i].second.first;
            grid[x][y] = 1;
        }
        if(!no){
            cout << "YES" << endl;
            for(int i = 0; i < n; i++){
                cout << c[i].second.second + 1 << endl;
            }
            return 0;
        }
        for(int i = 0; i < 2 * n ;i++){
            for(int j = 0; j < 2 * n; j++) {
                grid[i][j] = vs[i][j] = 0;
            }
        }
        
    }while(next_permutation(c.begin(), c.end()));
    cout << "NO";
    
    return 0;
}

Compilation message

skyscrapers.cpp: In function 'bool check()':
skyscrapers.cpp:31: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]
   31 |     while(j < b.size()){
      |           ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Incorrect 0 ms 340 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Incorrect 0 ms 340 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Incorrect 0 ms 340 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB ans=NO N=1934
2 Correct 1 ms 468 KB ans=NO N=1965
3 Execution timed out 3585 ms 119712 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Incorrect 0 ms 340 KB Full cells must be connected
5 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8504 KB ans=NO N=66151
2 Correct 37 ms 5508 KB ans=NO N=64333
3 Runtime error 828 ms 833560 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 596 KB ans=NO N=1934
2 Correct 1 ms 468 KB ans=NO N=1965
3 Execution timed out 3585 ms 119712 KB Time limit exceeded
4 Halted 0 ms 0 KB -