Submission #564652

#	Time	Username	Problem	Language	Result	Execution time	Memory
564652		Majid	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	336 ms	19144 KiB

skyscrapers

#include<bits/stdc++.h>
using namespace std;
 
//Types
using ll = long long;
using db = double;
 
//Vectors
#define pb push_back
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(), vec.end()
 
//things
#define f first
#define s second
const int SMALLINF = 1e9 + 7;
const ll BIGINF = ((ll)1e18) + 7;
#define Speeed ios::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);

ll dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
ll dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};

// struct info{
// 
//     ll x, y, pos;
// };

void solve(){

    ll n, t;
    cin>>n>>t;
    
    vector<pair<ll, ll> > vec(n);
    vector<pair<ll, pair<ll, ll> > > ex(n);
    map<pair<ll, ll>, bool> visited, exist;
    map<pair<ll, ll>, ll> order;
    
    for(ll i = 0; i < n; i++){
        
        cin>>ex[i].s.f>>ex[i].s.s;
        ex[i].f = i+1;
    }
    
    sort(all(ex));
    
    for(ll i = 0; i < n; i++){
        
        vec[i].f = ex[i].s.f;
        vec[i].s = ex[i].s.s;
        
        pair<ll, ll> p;
        p.f = vec[i].f;
        p.s = vec[i].s;

        exist[p] = true;
        order[p] = i+1;
    }
    
    
    sort(all(vec));
    visited[vec[0]] = true;
    
    priority_queue<pair<ll, pair<ll, ll> >, vector<pair<ll, pair<ll, ll> > >, greater<pair<ll, pair<ll, ll> > > > pq;
    pq.push({order[vec[0]], vec[0]});
        
    vector<ll> res;
    while(sz(pq)){
    
            ll x = pq.top().s.f, y = pq.top().s.s, pos = pq.top().f;
            pq.pop();
    
            for(ll i = 0; i < 8; i++){
    
                pair<ll, ll> pch;
                pch.f = x+dx[i], pch.s = y+dy[i];
    
                if(exist[pch] and !visited[pch]){
    
                        visited[pch] = true;
                        pair<ll, pair<ll, ll>> qq;
                        qq.s.f = pch.f;
                        qq.s.s = pch.s;
                        qq.f = order[pch];
    
                        pq.push(qq); 
                    }
                }
                res.pb(pos);
            }
    
    if(sz(res)==n){
    
        cout<<"YES\n";
        for(ll i = 0; i < sz(res); i++){
    
            cout<<res[i]<<" ";
        }
    }
    
    else cout<<"NO\n";
}


int main(){
	Speeed
	
    ll t=1;
    // cin>>t;
    
    while(t--){
        
        solve();
    }
}

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