#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991
const int maxn = 150001;
const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int inv[] = {4, 5, 6, 7, 0, 1, 2, 3};
struct cell;
int n, t, ID;
cell* Find (cell *x);
void check (cell *c);
void Union (cell *a, cell *b);
map<pair<int,int>, cell*> cells;
struct cell {
bool full, out;
int x, y, ind;
cell* adj[8], *parent = this, *prev = nullptr;
vector<cell*> vec;
cell(int a, int b, bool f) {
full = f;
x = a, y = b;
cells[{x, y}] = this;
if (f) ind = ID;
if (f == 0) vec = {this};
for (int d = 0 ; d < 8 ; d++) {
int u = x + dx[d];
int v = y + dy[d];
auto it = cells.find({u, v});
if (it != cells.end()) {
adj[d] = it -> second;
it -> second -> adj[inv[d]] = this;
}
else adj[d] = nullptr;
}
if (f == 0) {
for (int d = 0 ; d < 8 ; d += 2) {
if (adj[d] and !adj[d] -> full) Union(this, adj[d]);
}
}
}
};
cell* inp[maxn];
struct cmp {
bool operator () (cell *a, cell *b) const {
return a -> ind > b -> ind;
}
};
set<cell*,cmp> expendable;
cell* Find (cell *x) {
return x == x -> parent ? x : x -> parent = Find(x -> parent);
}
void check (cell *c) {
int u = c -> x, v = c -> y, ind = c -> ind;
bool articulation = 0, isout = 0, sep;
for (int i = 0 ; i < 8 ; i++) {
if (c -> adj[i] and !c -> adj[i] -> full) isout |= Find(c -> adj[i]) -> out;
}
if (!isout) {
expendable.erase(c);
return;
}
for (int _d = 0 ; _d < 9 ; _d++) {
int d = (_d == 8 ? 0 : _d);
if (!c -> adj[d]) return;
if (c -> adj[d] -> full) {
sep = 1;
continue;
}
if (d & 1) continue;
auto cmp = Find(c -> adj[d]);
if (cmp -> prev and sep == 1) {
bool bad = 0;
for (int __d = _d ; !bad ; __d++) {
int d2 = __d % 8;
if (c -> adj[d2] == cmp -> prev) break;
if (c -> adj[d2] -> full) bad = 1;
}
if (bad) articulation = 1;
}
cmp -> prev = c -> adj[d];
sep = 0;
}
for (int d = 0 ; d < 8 ; d++) {
if (!c -> adj[d] -> full) Find(c -> adj[d]) -> prev = nullptr;
}
if (isout and !articulation) expendable.insert(c);
else expendable.erase(c);
}
void Union (cell *a, cell *b) {
cell *x = Find(a), *y = Find(b);
if (x -> vec > y -> vec) swap(x, y);
for (auto &i : x -> vec) {
for (int d = 0 ; d < 8 ; d++) if (i -> adj[d] and i -> adj[d] -> full) check(i -> adj[d]);
y -> vec.push_back(i);
}
x -> vec.clear();
}
signed main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> t;
for (int i = 0 ; i < n ; i++) {
ID = i;
int x, y;
cin >> x >> y;
inp[i] = new cell(x, y, 1);
}
for (int i = 0 ; i < n ; i++) {
for (int d = 0 ; d < 8 ; d++) {
if (!inp[i] -> adj[d]) inp[i] -> adj[d] = new cell(inp[i] -> x + dx[d], inp[i] -> y + dy[d], 0);
}
}
if (n > 1) {
for (int i = 0 ; i < n ; i++) {
bool good = 0;
for (int d = 0 ; d < 8 ; d++) {
if (inp[i] -> adj[d] -> full) good = 1;
}
if (!good) {
cout << "NO\n";
return 0;
}
}
}
for (int i = 0 ; i < n ; i++) check(inp[i]);
cout << "YES\n";
vector<int> ans;
while (expendable.size()) {
auto cur = *expendable.begin();
expendable.erase(expendable.begin());
ans.push_back(cur -> ind + 1);
*cur = cell(cur -> x, cur -> y, 0);
}
reverse(ans.begin(), ans.end());
for (int i: ans) cout << i << endl;
}
Compilation message
skyscrapers.cpp:17:1: warning: multi-line comment [-Wcomment]
17 | //\
| ^
skyscrapers.cpp: In function 'void check(cell*)':
skyscrapers.cpp:77:9: warning: unused variable 'u' [-Wunused-variable]
77 | int u = c -> x, v = c -> y, ind = c -> ind;
| ^
skyscrapers.cpp:77:21: warning: unused variable 'v' [-Wunused-variable]
77 | int u = c -> x, v = c -> y, ind = c -> ind;
| ^
skyscrapers.cpp:77:33: warning: unused variable 'ind' [-Wunused-variable]
77 | int u = c -> x, v = c -> y, ind = c -> ind;
| ^~~
skyscrapers.cpp:95:25: warning: 'sep' may be used uninitialized in this function [-Wmaybe-uninitialized]
95 | if (cmp -> prev and sep == 1) {
| ~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
4808 KB |
ans=NO N=1934 |
| 2 |
Correct |
9 ms |
1620 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
3 ms |
724 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
23528 KB |
ans=NO N=66151 |
| 2 |
Correct |
952 ms |
117580 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
150 ms |
15944 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
4808 KB |
ans=NO N=1934 |
| 2 |
Correct |
9 ms |
1620 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
3 ms |
724 KB |
Unexpected end of file - int32 expected |
| 4 |
Halted |
0 ms |
0 KB |
- |
