#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <bitset>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define mp make_pair
using namespace std;
const ll mod = 998244353;
const int nmax = 200001;
set <int> st[nmax];
int cnt[nmax];
set <int> good;
vector <vector <int> > vv(nmax);
bool out[nmax];
vector <int> p(nmax);
map <pii, int> m;
bool used[nmax];
int x[nmax], y[nmax];
vector <pii> d;
int n;
void dfs(int x, int y){
used[m[mp(x, y)]] = true;
for(int i = 0; i < d.size(); i++){
int nx = x + d[i].f, ny = y + d[i].s;
if(!m[mp(nx, ny)]) continue;
if(used[m[mp(nx, ny)]]) continue;
dfs(nx, ny);
}
}
bool A[nmax], B[nmax];
int cur;
void make_set(int v){
p[v] = v;
// out[v] = true;
// sz[v] = 1;
}
int find_set(int v){
return p[v] == v ? v : p[v] = find_set(p[v]);
}
void rem(int ind){
good.erase(ind);
B[ind] = false;
}
void add(int ind){
if(cnt[ind] == st[ind].size()) B[ind] = true;
if(A[ind] && B[ind])good.insert(ind);
}
void union_sets(int a, int b){
a = find_set(a);
b= find_set(b);
if(a == b) return;
if(vv[a].size() < vv[b].size()) swap(a, b);
for(int i = 0; i < vv[b].size(); i++){
int x = vv[b][i];
rem(x);
st[x].erase(b);
st[x].insert(a);
add(x);
vv[a].pb(x);
}
p[b] = a;
out[a] |= out[b];
}
void recount_regions(int ind){
int lst = 0;
cnt[ind] = 0;
A[ind] = false;
B[ind] = false;
good.erase(ind);
for(int i = 0; i < d.size(); i++){
int nx = x[ind] + d[i].f, ny = y[ind] + d[i].s;
if(m[mp(nx, ny)] > n) {
lst = 1;
A[ind] |= out[find_set(m[mp(nx, ny)])];
}
else{ if(lst == 1) cnt[ind]++; lst =0;}
}
if(!cnt[ind]) cnt[ind]++;
if(cnt[ind] == st[ind].size()) B[ind] = true;
if(A[ind] && B[ind]) good.insert(ind);
}
void make_empty(int ind){
m[mp(x[ind], y[ind])] = cur++;
make_set(cur - 1);
for(int i = 0; i < d.size(); i++){
int nx = d[i].f + x[ind], ny = d[i].s + y[ind];
if(m[mp(nx, ny)] > n) union_sets(cur - 1, m[mp(nx, ny)]);
}
for(int i = 0; i < d.size(); i++){
int nx = d[i].f + x[ind], ny = d[i].s + y[ind];
pii o = mp(nx, ny);
if(m[o] > 0 && m[o] <= n) recount_regions(m[o]);
}
}
int main(){
d.pb(mp(-1, -1)); d.pb(mp(-1, 0)); d.pb(mp(-1, 1));
d.pb(mp(0, 1)); d.pb(mp(1, 1)); d.pb(mp(1, 0)); d.pb(mp(1, -1));
d.pb(mp(0, -1)); d.pb(mp(-1, -1));
cin >> n;
int t; cin >> t;
cur = n + 1;
int mxx, mxy;
mxy= mxx = -1e9 + 10;
int mnx, mny;
mnx = mny = 1e9 + 10;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
mxx = max(mxx, x[i]);
mnx = min(mnx, x[i]);
mxy = max(mxy, y[i]);
mny = min(mny, y[i]);
m[mp(x[i], y[i])] = i;
}
dfs(x[1], y[1]);
for(int i = 1; i <= n; i++){
if(!used[i]){
cout << "NO\n";
return 0;
}
}
vector <pii> empt;
for(int i = 1; i <= n; i++){
for(int j = 0; j < d.size(); j++){
int nx = x[i] + d[j].f, ny = y[i] + d[j].s;
if(!m[mp(nx, ny)]){
make_set(cur);
if(nx < mnx || ny < mny || nx > mxx || ny > mxy)
out[cur] = true;
empt.pb(mp(nx, ny));
m[mp(nx, ny)] = cur++;
}
if(m[mp(nx, ny)] > n) st[i].insert(m[mp(nx, ny)]),
vv[m[mp(nx, ny)]].pb(i);
}
}
for(int i = 1; i <= n; i++)
recount_regions(i);
for(int i = 0; i <empt.size(); ++i){
int x = empt[i].f, y = empt[i].s;
for(int j = 0; j < d.size(); j++){
int nx = x + d[j].f, ny = y + d[j].s;
if(m[mp(nx, ny)] > n){
union_sets(m[empt[i]], m[mp(nx, ny)]);
}
}
}
vector <int> ans;
while(!good.empty()){
ans.pb(*good.rbegin());
good.erase(ans.back());
make_empty(ans.back());
}
cout << "YES\n";
reverse(ans.begin(), ans.end());
for(int i =0 ; i < ans.size(); i++){
cout << ans[i] << "\n";
}
return 0;
}
Compilation message
skyscrapers.cpp: In function 'void dfs(int, int)':
skyscrapers.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < d.size(); i++){
| ~~^~~~~~~~~~
skyscrapers.cpp: In function 'void add(int)':
skyscrapers.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if(cnt[ind] == st[ind].size()) B[ind] = true;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void union_sets(int, int)':
skyscrapers.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < vv[b].size(); i++){
| ~~^~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void recount_regions(int)':
skyscrapers.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < d.size(); i++){
| ~~^~~~~~~~~~
skyscrapers.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if(cnt[ind] == st[ind].size()) B[ind] = true;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~
skyscrapers.cpp: In function 'void make_empty(int)':
skyscrapers.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i = 0; i < d.size(); i++){
| ~~^~~~~~~~~~
skyscrapers.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0; i < d.size(); i++){
| ~~^~~~~~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int j = 0; j < d.size(); j++){
| ~~^~~~~~~~~~
skyscrapers.cpp:165:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for(int i = 0; i <empt.size(); ++i){
| ~~^~~~~~~~~~~~
skyscrapers.cpp:167:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int j = 0; j < d.size(); j++){
| ~~^~~~~~~~~~
skyscrapers.cpp:184:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int i =0 ; i < ans.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
ans=YES N=1 |
| 2 |
Correct |
7 ms |
15188 KB |
ans=YES N=4 |
| 3 |
Correct |
9 ms |
15188 KB |
ans=NO N=4 |
| 4 |
Correct |
7 ms |
15188 KB |
ans=YES N=5 |
| 5 |
Incorrect |
9 ms |
15164 KB |
Unexpected end of file - int32 expected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
ans=YES N=1 |
| 2 |
Correct |
7 ms |
15188 KB |
ans=YES N=4 |
| 3 |
Correct |
9 ms |
15188 KB |
ans=NO N=4 |
| 4 |
Correct |
7 ms |
15188 KB |
ans=YES N=5 |
| 5 |
Incorrect |
9 ms |
15164 KB |
Unexpected end of file - int32 expected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
ans=YES N=1 |
| 2 |
Correct |
7 ms |
15188 KB |
ans=YES N=4 |
| 3 |
Correct |
9 ms |
15188 KB |
ans=NO N=4 |
| 4 |
Correct |
7 ms |
15188 KB |
ans=YES N=5 |
| 5 |
Incorrect |
9 ms |
15164 KB |
Unexpected end of file - int32 expected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
15328 KB |
ans=NO N=1934 |
| 2 |
Correct |
9 ms |
15356 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
18 ms |
15632 KB |
Full cells must be connected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15188 KB |
ans=YES N=1 |
| 2 |
Correct |
7 ms |
15188 KB |
ans=YES N=4 |
| 3 |
Correct |
9 ms |
15188 KB |
ans=NO N=4 |
| 4 |
Correct |
7 ms |
15188 KB |
ans=YES N=5 |
| 5 |
Incorrect |
9 ms |
15164 KB |
Unexpected end of file - int32 expected |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
27972 KB |
ans=NO N=66151 |
| 2 |
Correct |
46 ms |
19692 KB |
ans=NO N=64333 |
| 3 |
Incorrect |
386 ms |
28740 KB |
Full cells must be connected |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
15328 KB |
ans=NO N=1934 |
| 2 |
Correct |
9 ms |
15356 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
18 ms |
15632 KB |
Full cells must be connected |
| 4 |
Halted |
0 ms |
0 KB |
- |
