Submission #260974

#	Time	Username	Problem	Language	Result	Execution time	Memory
260974		trainee	Building Skyscrapers (CEOI19_skyscrapers)	C++17	54 / 100	544 ms	26740 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define rep(i,a,n) for(int i = a; i<n; i++)
#define per(i,a,n) for(int i = n-1; i>=a; i--)

map<pair<int,int>,bool> vis;
map<pair<int,int>,int> idx;
int n,t;

int max(int a,int b){return (a>b)?a:b;}
int min(int a,int b){return (a<b)?a:b;}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>t;
    bool f = false;
    pair<int,int> start = make_pair(-1,-1);
    rep(i,0,n){
        int x,y;
        cin>>x>>y;
        idx[make_pair(x,y)] = i+1;
        vis[make_pair(x,y)] = false;
        if(!f || x > start.first)start = make_pair(x,y),f = true;
    }

    priority_queue<pair<int,int> > pq;
    vector<pair<int,int> > res;
    pq.push(start);
    vis[start] = true;
    while(!pq.empty()){
        pair<int,int> node = pq.top();
        pq.pop();
        res.push_back(node);
        rep(i,-1,2){
         rep(j,-1,2){
            if(i==0&&j==0)continue;
            pair<int,int> e = node;
            e.first += i;
            e.second += j;
            if(vis.find(e) != vis.end() && !vis[e]){
                vis[e] = true;
                pq.push(e);
            }
        }   
        }

    }
    bool works = true;
    for(auto i:vis){
        works &= i.second;
    }
    if(works){
        cout<<"YES\n";
        for(auto i:res){
            cout<<idx[i]<<" ";
        }
        cout<<"\n";
    }else{
        cout<<"NO\n";
    }


}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 0 / 17
• Subtask 5: 20 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19