Submission #943929

#	Time	Username	Problem	Language	Result	Execution time	Memory
943929		vjudge1	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	94 ms	32524 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};
ll x[N],y[N];
map<pair<ll,ll>,ll> mp,vis;
vll ans;
void bfs(ll s){
    set<pair<ll,ll>> st;
    st.ins({x[s],y[s]});
    while(st.sz){
        ll x1=st.begin()->fr,y1=st.begin()->sc;
        ans.pb(mp[{x1,y1}]);
        st.erase(st.begin());
        for(ll i=0;i<10;i++){
            ll nx=x1+xd[i],ny=y1+yd[i];
            if(!vis[{nx,ny}]){
                vis[{nx,ny}]=1;
                st.ins({nx,ny});
            }
        }
    }
}
void solve(){
    ll i,j;
    ll n,t;
    cin>>n>>t;
    ll sx=inf,sy=inf;
    for(i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        mp[{x[i],y[i]}]=i;
        if(sx>x[i] || (sx==x[i] && sy>y[i])) sx=x[i],sy=y[i];
    }
    bfs(mp[{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:75: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]
   75 |     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