Submission #1277485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277485		MisterReaper	Building Skyscrapers (CEOI19_skyscrapers)	C++20	61 / 100	3595 ms	53136 KiB

skyscrapers

// File skyscrapers.cpp created on 09.10.2025 at 09:27:26
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int dxa[] = {+1, 0, -1, 0};
constexpr int dya[] = {0, +1, 0, -1};

int N, T;
std::vector<std::pair<int, int>> A;

std::set<std::pair<int, int>> blacks;
std::map<std::pair<int, int>, int> id;

std::map<std::pair<int, int>, bool> reached;
void dfs(int x, int y) {
    if (!id.contains({x, y}) || reached[{x, y}]) {
        return;
    }
    reached[{x, y}] = true;
    for (int dx = -1; dx <= 1; ++dx) {
        for (int dy = -1; dy <= 1; ++dy) {
            int nx = x + dx;
            int ny = y + dy;
            dfs(nx, ny);
        }
    }
}

struct DSU {
    std::vector<int> f, siz;
    void init(int n) {
        f.assign(n, 0);
        siz.assign(n, 1);
        std::iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        } else if (siz[a] > siz[b]) {
            std::swap(a, b);
        }
        f[a] = b;
        siz[b] += siz[a];
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return siz[get(x)];
    }
} dsu;
std::vector<int> vis;
std::vector<int> push;
std::vector<int> onpq;
std::priority_queue<std::tuple<int, int, int>> pq;

bool is_black(int x, int y) {
    if (blacks.contains({x, y}) && !push[id[{x, y}]]) {
        return true;
    }
    return false;
}

bool check(int x, int y) {
    if (!is_black(x, y)) {
        return false;
    }
    debug("check", x, y);
    int cnt = 0;
    for (int dx = -1; dx <= 1; ++dx) {
        for (int dy = -1; dy <= 1; ++dy) {
            if (dx == 0 && dy == 0) {
                continue;
            }
            int nx = x + dx;
            int ny = y + dy;
            cnt += is_black(nx, ny);
        }
    }
    {
        if (dsu.same(id[{x + 1, y}], id[{x - 1, y}])) {
            int a = is_black(x + 1, y - 1) + is_black(x, y - 1) + is_black(x - 1, y - 1); 
            int b = is_black(x + 1, y + 1) + is_black(x, y + 1) + is_black(x - 1, y + 1); 
            if (a && b) {
                return false;
            }
        }
    }
    {
        if (dsu.same(id[{x, y + 1}], id[{x, y - 1}])) {
            int a = is_black(x + 1, y - 1) + is_black(x + 1, y) + is_black(x + 1, y + 1); 
            int b = is_black(x - 1, y - 1) + is_black(x - 1, y) + is_black(x - 1, y + 1); 
            if (a && b) {
                return false;
            }
        }
    }
    for (int d = 0; d < 4; ++d) {
        int nx0 = x + dxa[d];
        int ny0 = y + dya[d];
        int nx1 = x + dxa[(1 + d) % 4];
        int ny1 = y + dya[(1 + d) % 4];
        int nx2 = x + dxa[d] + dxa[(1 + d) % 4];
        int ny2 = y + dya[d] + dya[(1 + d) % 4];
        if (dsu.same(id[{nx0, ny0}], id[{nx1, ny1}])
         && is_black(nx2, ny2)) {
            debug(nx0, ny0);
            debug(nx1, ny1);
            debug(nx2, ny2);
            debug(d, cnt);
            int ncnt = cnt - is_black(nx0, ny0) - is_black(nx1, ny1) - is_black(nx2, ny2);
            if (ncnt > 0) {
                // debug("second step", d);
                return false;
            }
        }
    }
    return true;
}

void domerge(int x, int y) {
    assert(id.contains({x, y}) && !is_black(x, y));
    for (int d = 0; d < 4; ++d) {
        int nx = x + dxa[d];
        int ny = y + dya[d];
        if (!id.contains({nx, ny}) || is_black(nx, ny)) {
            continue;
        }
        if (dsu.unite(id[{x, y}], id[{nx, ny}])) {
            // debug("dsu", x, y, nx, ny);
        }
    }
}

void push_pq(int x, int y) {
    for (int dx = -1; dx <= 1; ++dx) {
        for (int dy = -1; dy <= 1; ++dy) {
            int nx = x + dx;
            int ny = y + dy;
            if (!is_black(nx, ny) || !vis[id[{nx, ny}]] || onpq[id[{nx, ny}]]) {
                continue;
            }
            if (check(nx, ny)) {
                onpq[id[{nx, ny}]] = true;
                pq.emplace(id[{nx, ny}], nx, ny);
            }
        }
    }
}

void fill(int x, int y) {
    if (is_black(x, y)) {
        if (vis[id[{x, y}]]) {
            return;
        }
        vis[id[{x, y}]] = true;
        push_pq(x, y);
    } else {
        if (vis[id[{x, y}]]) {
            return;
        }
        vis[id[{x, y}]] = true;
        push_pq(x, y);
        for (int d = 0; d < 4; ++d) {
            int nx = x + dxa[d];
            int ny = y + dya[d];
            if (id.contains({nx, ny})) {
                fill(nx, ny);
            }
        }
    }
}

bool checker_answer(std::vector<int> ord) {
    for (int i = 1; i < N; ++i) {
        bool ok = false;
        for (int j = 0; j < i; ++j) {
            int x = ord[i];
            int y = ord[j];
            if (std::abs(A[x].first - A[y].first) <= 1 && std::abs(A[x].second - A[y].second) <= 1) {
                ok = true;
                break;
            }
        }
        if (!ok) {
            return false;
        }
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> T;

    A.resize(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i].first >> A[i].second;
        id[A[i]] = i;
        blacks.emplace(A[i]);
    }

    dfs(A[0].first, A[0].second);

    if (reached.size() != id.size()) {
        std::cout << "NO\n";
        return 0;
    }

    int cnt = N;
    for (auto[x, y] : A) {
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                int nx = x + dx;
                int ny = y + dy;
                if (!id.contains({nx, ny})) {
                    id[{nx, ny}] = cnt;
                    cnt++;
                }
            }
        }
    }

    std::pair<int, int> pnt = A[0];
    for (auto[x, _] : id) {
        pnt = std::min(pnt, x);
    }

    vis.assign(id.size(), 0);
    onpq.assign(N, 0);
    push.assign(N, 0);
    dsu.init(id.size());
    fill(pnt.first, pnt.second);

    for (auto[x, _] : id) {
        if (!is_black(x.first, x.second)) {
            domerge(x.first, x.second);
        }
    }

    std::vector<int> ans;
    while (!pq.empty()) {
        auto[val, x, y] = pq.top();
        pq.pop();
        onpq[val] = false;
        if (!check(x, y)) {
            continue;
        }
        debug("black", x, y);
        debug();
        debug();
        debug();
        debug();
        push[id[{x, y}]] = 1;
        vis[id[{x, y}]] = 0;
        domerge(x, y);
        fill(x, y);
        ans.emplace_back(id[{x, y}]);
    }

    debug(ans);

    assert(int(ans.size()) == N);

    std::reverse(ans.begin(), ans.end());

    std::cout << "YES\n";
    for (auto i : ans) {
        std::cout << i + 1 << " \n"[i == ans.back()];
    }

    // assert(checker_answer(ans));

    return 0;
}

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