Submission #943938

#	Time	Username	Problem	Language	Result	Execution time	Memory
943938		vjudge1	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	31 ms	9272 KiB

skyscrapers

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=2e5+5;
const ld eps=1e-9;
ll xd[9]={-1,-1,-1,0,0,1,1,1},yd[9]={-1,0,1,-1,1,-1,0,1};
map<pair<ll,ll>,ll> mp,vis;
vll ans;
void bfs(ll x,ll y){
    set<pair<ll,ll>> st;
    st.ins({x,y});
    vis[{x,y}]=1;
    while(st.sz){
        x=st.begin()->fr,y=st.begin()->sc;
        ans.pb(mp[{x,y}]);
        st.erase(st.begin());
        for(ll i=0;i<10;i++){
            ll nx=x+xd[i],ny=y+yd[i];
            if(!vis[{nx,ny}] && mp[{nx,ny}]){
                vis[{nx,ny}]=1;
                st.ins({nx,ny});
            }
        }
    }
}
void solve(){
    ll i,j;
    ll n,t;
    cin>>n>>t;
    ll x,y;
    ll sx=inf,sy=inf;
    for(i=1;i<=n;i++){
        cin>>x>>y;
        mp[{x,y}]=i;
        if(sx>x || (sx==x && sy>y)) {sx=x;sy=y;}
    }
    bfs(sx,sy);
    if(ans.sz!=n){
        cout<<"NO"<<endl;
        return;
    }
    cout<<"YES"<<endl;
    for(auto i : ans) cout<<i<<endl;
}

signed main(){
	start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*




*/

Compilation message (stderr)

skyscrapers.cpp: In function 'void solve()':
skyscrapers.cpp:76:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   76 |     if(ans.sz!=n){
      |        ~~~~~~^~~
skyscrapers.cpp:65:10: warning: unused variable 'j' [-Wunused-variable]
   65 |     ll i,j;
      |          ^

• 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