// 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) || 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |