Submission #501077

#	Time	Username	Problem	Language	Result	Execution time	Memory
501077		InternetPerson10	Building Skyscrapers (CEOI19_skyscrapers)	C++17	8 / 100	3563 ms	40616 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v;

int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dxe[4] = {-1, 0, 1, 0};
int dye[4] = {0, 1, 0, -1};

map<pair<int, int>, int> m;
set<pair<int, int>> black;

struct dsu {
    vector<int> par, siz;
    void init(int n) {
        vector<int>().swap(par);
        vector<int>().swap(siz);
        par.resize(n);
        siz.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(x == par[x]) return x;
        return par[x] = get(par[x]);
    }
    bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if(x == y) return false;
        if(x < y) swap(x, y); // y is the lesser one now
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};


vector<int> find_order(int n, vector<int> x, vector<int> y) {
    vector<int> ans;
    return ans;
}

vector<int> find_best_order(int n, vector<int> x, vector<int> y) {
    vector<int> ans;
    int mix, miy;
    mix = miy = 1234567890;
    for(int i = 0; i < n; i++) {
        mix = min(mix, x[i]);
        miy = min(miy, y[i]);
    }
    mix--;
    miy--;
    for(int i = 0; i < n; i++) {
        x[i] -= mix;
        y[i] -= miy;
        v.push_back({x[i], y[i]});
        black.insert({x[i], y[i]});
        for(int j = 0; j < 8; j++) {
            v.push_back({x[i]+dx[j], y[i]+dy[j]});
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // Vertex labels are stored as an unordered_map
    // I should constopt this if it's too slow
    for(int i = 0; i < v.size(); i++) {
        m[v[i]] = i;
    }
    dsu uf;
    uf.init(v.size()+1);
    // First check if the peple are connected
    bool ok = false;
    for(int i = 0; i < v.size(); i++) {
        if(black.count(v[i])) {
            for(int j = 0; j < 8; j++) {
                pair<int, int> oth_pair = {v[i].first+dx[j], v[i].second+dy[j]};
                if(black.count(oth_pair)) {
                    uf.unite(m[v[i]], m[oth_pair]);
                }
            }
            if(uf.siz[uf.get(m[v[i]])] == n) ok = true;
        }
    }
    if(!ok) return ans;
    // Now find an order, unite all white regions
    uf.init(v.size()+1);
    for(int i = 0; i < v.size(); i++) {
        if(black.count(v[i])) continue;
        for(int j = 0; j < 4; j++) {
            pair<int, int> oth_pair = {v[i].first+dxe[j], v[i].second+dye[j]};
            if(black.count(oth_pair)) continue;
            uf.unite(m[v[i]], m[oth_pair]);
        }
    }
    ans.reserve(n);
    for(int z = 0; z < n; z++) {
        for(int i = 0; i < n; i++) { // Checks if the regions around the cell are "good"
            pair<int, int> this_pair = {x[i], y[i]};
            // cout << x[i] << ' ' << y[i] << '\n';
            if(!black.count(this_pair)) continue;
            vector<int> regs;
            for(int j = 0; j < 4; j++) {
                pair<int, int> oth_pair = {x[i]+dxe[j], y[i]+dye[j]};
                if(black.count(oth_pair)) regs.push_back(-1); 
                else regs.push_back(uf.get(m[oth_pair]));
                oth_pair = {x[i]+dx[(2*j+2)%8], y[i]+dy[(2*j+2)%8]};
                if(black.count(oth_pair)) regs.push_back(-1);
            }
            /*
            cout << z << ' ' << i << " | ";
            for(int g : regs) cout << g << ' ';
            cout << '\n';
            */
            while(regs[0] == regs.back() && regs.size() > 1) regs.pop_back();
            regs.erase(unique(regs.begin(), regs.end()), regs.end());
            regs.erase(remove(regs.begin(), regs.end(), -1), regs.end());
            if(regs.size() == 1 && regs[0] == 0) {
                black.erase(this_pair);
                ans.push_back(i+1);
                uf.unite(m[this_pair], 0);
                break;
            }
            if(regs.size() == 1) continue;
            sort(regs.begin(), regs.end());
            /*
            for(int g : regs) cout << g << ' ';
            cout << '\n';
            */
            if(regs[0] != 0) continue;
            bool ok = true;
            for(int i = 1; i < regs.size(); i++) {
                if(regs[i] == regs[i-1]) ok = false;
            }
            if(!ok) continue;
            black.erase(this_pair);
            ans.push_back(i+1);
            uf.unite(m[this_pair], 0);
            for(int i = 1; i < regs.size(); i++) {
                uf.unite(regs[i-1], regs[i]);
            }
            break;
        }
        if(ans.size() == z-1) {
            vector<int>().swap(ans);
            return ans;
        }
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    int n, s;
    cin >> n >> s;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    vector<int> ans;
    if(s == 1) ans = find_best_order(n, x, y);
    if(s == 2) ans = find_best_order(n, x, y);
    if(ans.size() == 0) {
        cout << "NO\n";
    }
    else {
        cout << "YES\n";
        for(int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

skyscrapers.cpp: In function 'std::vector<int> find_best_order(int, std::vector<int>, std::vector<int>)':
skyscrapers.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
skyscrapers.cpp:133:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             for(int i = 1; i < regs.size(); i++) {
      |                            ~~^~~~~~~~~~~~~
skyscrapers.cpp:140:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |             for(int i = 1; i < regs.size(); i++) {
      |                            ~~^~~~~~~~~~~~~
skyscrapers.cpp:145:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  145 |         if(ans.size() == z-1) {
      |            ~~~~~~~~~~~^~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:169:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for(int i = 0; i < ans.size(); i++) cout << ans[i] << '\n';
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 8 / 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