Submission #798491

#	Time	Username	Problem	Language	Result	Execution time	Memory
798491		Ronin13	Building Skyscrapers (CEOI19_skyscrapers)	C++17	54 / 100	269 ms	42440 KiB

skyscrapers

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <bitset>

#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define mp make_pair

using namespace std;

const ll mod = 998244353;

vector <int> d;



int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int type; cin >> type;
    set <pair<pii, int> > st;
    vector <int> ans;
    pii mn = mp(1e9 + 1, 1e9 + 1);
    int mni;
    map <pii, int> m;
    int x[n + 1], y[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        m[mp(x[i], y[i])] = i; 
        if(mn > mp(x[i], y[i]))
            mn = mp(x[i], y[i]), mni = i;
    }
    st.insert(mp(mn, mni));
    m[mn] = 0;
    d.pb(-1); d.pb(0); d.pb(1);
    while(!st.empty()){
        int x = st.begin()->s;
        pii o = st.begin()->f;
        st.erase(st.begin());
        ans.pb(x);
        for(int i = 0; i < 3; i++){
            int curx = o.f, cury = o.s;
            for(int j = 0; j < 3; j++){
                int nx = curx + d[i];
                int ny = cury + d[j];
                if(m[mp(nx, ny)]){
                    st.insert(mp(mp(nx, ny), m[mp(nx, ny)])), m[mp(nx, ny)] = 0;
                }
            }
        }
    }
    if(ans.size() == n){
        cout << "YES\n";
        for(int i = 0; i < ans.size(); ++i){
            cout << ans[i] << ' ';
        }
    }
    else cout << "NO\n";
    return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:63:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     if(ans.size() == n){
      |        ~~~~~~~~~~~^~~~
skyscrapers.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 0; i < ans.size(); ++i){
      |                        ~~^~~~~~~~~~~~
skyscrapers.cpp:44:25: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     st.insert(mp(mn, mni));
      |                         ^

• 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