Submission #703111

#	Time	Username	Problem	Language	Result	Execution time	Memory
703111		Cyanmond	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	329 ms	16296 KiB

skyscrapers

#include <bits/stdc++.h>

struct Point {
    int r, c;
};
auto compPoint = [](const Point &a, const Point &b) {
    if (a.r != b.r) {
        return a.r < b.r;
    }
    return a.c < b.c;
};
auto compPointPair = [](const std::pair<Point, Point> &a, const std::pair<Point, Point> &b) {
    if (not(a.first.r == b.first.r and a.first.c == b.first.c)) {
        return compPoint(a.first, b.first);
    } else {
        return compPoint(a.second, b.second);
    }
};

std::pair<int, int> dxy[8] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
std::pair<int, int> dxy2[4] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

int main() {
    int N, T;
    std::cin >> N >> T;
    std::vector<Point> sks(N);
    for (auto &[r, c] : sks) {
        std::cin >> r >> c;
    }
    std::map<Point, int, decltype(compPoint)> skMap(compPoint);
    std::set<Point, decltype(compPoint)> corners(compPoint);
    for (int i = 0; i < N; ++i) {
        skMap[sks[i]] = i;
        for (int a = 0; a <= 1; ++a) {
            for (int b = 0; b <= 1; ++b) {
                corners.insert({sks[i].r + a, sks[i].c + b});
            }
        }
    }

    // right-hand algo
    int minV = 0;
    for (int i = 0; i < N; ++i) {
        if (compPoint(sks[i], sks[minV])) {
            minV = i;
        }
    }
    const auto [initR, initC] = sks[minV];
    int nowR = initR, nowC = initC;
    int lastDrc = 1;
    std::set<std::pair<Point, Point>, decltype(compPointPair)> seenSides(compPointPair);
    auto addSide = [&](const Point &a, const Point &b) {
        if (compPoint(a, b)) seenSides.insert({a, b});
        else seenSides.insert({b, a});
    };
    do {
        lastDrc = (lastDrc + 2) % 4;
        for (int i = (lastDrc + 1) % 4; i != lastDrc; i = (i + 1) % 4) {
            const auto &[ax, ay] = dxy2[i];
            const int nx = nowR + ax, ny = nowC + ay;
            auto itr = corners.find({nx, ny});
            if (itr == corners.end()) {
                continue;
            }
            addSide({nowR, nowC}, {nx, ny});
            nowR = nx;
            nowC = ny;
            lastDrc = i;
            break;
        }
    } while (not(nowR == initR and nowC == initC));

    auto existSide = [&](const Point &a, const Point &b) {
        if (compPoint(a, b)) return seenSides.find({a, b}) != seenSides.end();
        else return seenSides.find({b, a}) != seenSides.end();
    };

    std::vector<bool> isSide(N);
    for (int i = 0; i < N; ++i) {
        const auto [r, c] = sks[i];
        if (existSide({r, c}, {r + 1, c})) isSide[i] = true;
        else if (existSide({r + 1, c}, {r + 1, c + 1})) isSide[i] = true;
        else if (existSide({r + 1, c + 1}, {r, c + 1})) isSide[i] = true;
        else if (existSide({r, c + 1}, {r, c})) isSide[i] = true;
    }

    std::vector<bool> isSeen(N);
    std::priority_queue<int> pq;
    for (int i = 0; i < N; ++i) {
        if (isSide[i]) {
            pq.push(i);
            isSeen[i] = true;
        }
    }

    std::vector<int> answer;
    while (not pq.empty()) {
        const auto f = pq.top();
        pq.pop();
        const auto &[r, c] = sks[f];
        answer.push_back(f);
        for (const auto &[ar, ac] : dxy) {
            const int nr = r + ar, nc = c + ac;
            auto itr = skMap.find({nr, nc});
            if (itr == skMap.end()) {
                continue;
            }
            const int t = itr->second;
            if (isSeen[t]) {
                continue;
            }
            isSeen[t] = true;
            pq.push(t);
        }
    }

    if (answer.size() != N) {
        std::cout << "NO" << std::endl;
    } else {
        std::cout << "YES" << std::endl;
        std::reverse(answer.begin(), answer.end());
        for (const auto e : answer) {
            std::cout << e + 1 << std::endl;
        }
    }
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:117:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     if (answer.size() != N) {
      |         ~~~~~~~~~~~~~~^~~~

• 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