Submission #518683

#	Time	Username	Problem	Language	Result	Execution time	Memory
518683		Monarchuwu	Building Skyscrapers (CEOI19_skyscrapers)	C++17	0 / 100	3535 ms	273252 KiB

skyscrapers

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 2e5 + 8;
const int dx[4] = { 1,-1,0,0 };
const int dy[4] = { 0,0,1,-1 };
int n, t;
struct Point {
    int x, y, id;
    Point() {}
    bool operator < (const Point &o) const {
        return y < o.y;
    }
} p[N];
int b[N], mx, my;
void compress() {
    for (int i = 1; i <= n; ++i) {
        b[++mx] = p[i].x - 1;
        b[++mx] = p[i].x;
        b[++mx] = p[i].x + 1;
    }
    sort(b + 1, b + mx + 1);
    mx = unique(b + 1, b + mx + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
        p[i].x = lower_bound(b + 1, b + mx + 1, p[i].x) - b;

    for (int i = 1; i <= n; ++i) {
        b[++my] = p[i].y - 1;
        b[++my] = p[i].y;
        b[++my] = p[i].y + 1;
    }
    sort(b + 1, b + my + 1);
    my = unique(b + 1, b + my + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
        p[i].y = lower_bound(b + 1, b + my + 1, p[i].y) - b;
}

vector<int> g[N];
bool vis[666][666], abc[666][666];
bool avail(int x, int y) {
    for (int i = 0; i < 606; ++i)
        for (int j = 0; j < 606; ++j)
            abc[i][j] = vis[i][j];

    queue<pii> q;
    q.emplace(x, y);
    abc[x][y] = true;
    while (!q.empty()) {
        x = q.front().ff, y = q.front().ss; q.pop();
        if (x == 0 || x == 601 || y == 0 || y == 601) return true;

        for (int i = 0; i < 4; ++i) {
            int xx = x + dx[i], yy = y + dy[i];
            if (!abc[xx][yy]) {
                abc[xx][yy] = true;
                q.emplace(xx, yy);
            }
        }
    }
    return false;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> t;
    for (int i = 1; i <= n; ++i)
        cin >> p[i].x >> p[i].y, p[i].id = i;
    sort(p + 1, p + n + 1);
    compress();

    for (int i = 1; i < n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            if (abs(p[i].x - p[i].x) <= 1 && abs(p[i].y - p[j].y) <= 1) {
                g[p[i].id].push_back(p[j].id);
                g[p[j].id].push_back(p[i].id);
            }
        }

    vector<int> ans(1, p[1].id);
    vis[p[1].x][p[1].y] = true;
    queue<int> q;
    q.push(p[1].id);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (!vis[p[v].x][p[v].y]) {
            if (avail(p[v].x, p[v].y))
                ans.push_back(p[v].id);
            else ans.insert(ans.begin(), p[v].id);

            vis[p[v].x][p[v].y] = true;
            q.push(p[v].id);
        }
    }

    if (ans.size() != n) cout << "NO\n";
    else {
        cout << "YES\n";
        for (int x : ans) cout << x << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:105:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |     if (ans.size() != n) cout << "NO\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