#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
int grid[5001][5001],vs[5001][5001],w[5001][5001];
int x[] = {-1,-1,-1,0,1,1,1,0}, y[] = {-1,0,1,1,1,0,-1,-1};
int xx[] = {0,0,1,-1}, yy[] = {1,-1,0,0};
vector<pair<int,int>>p;
vector<pair<int,int>>nxt;
vector<int>ans;
int n;
bool cmp(int* a, int *b){
return *a < *b;
}
bool check(){
vector<pair<int,int>>b;
b.push_back({p[0].first,p[0].second});
set<pair<int,int>>c,d;
for(int i = 1; i < n; i++){
d.insert({p[i].first,p[i].second});
}
int j = 0;
while(j < b.size()){
for(int k = 0; k < 8; k++){
int nx = b[j].first + x[k], ny = b[j].second + y[k];
if(d.count({nx,ny})){
d.erase({nx,ny});
b.push_back({nx,ny});
}
}
j++;
}
return d.empty();
}
void dfs(int a, int b){
vs[a][b] = 1;
//cout << a << ' ' << b << endl;
if(grid[a][b]){
nxt.push_back({a,b});
return;
}
for(int k = 0; k < 4; k++){
int aa = a + xx[k], bb = b + yy[k];
if(aa < 0 || bb < 0 || aa >= 2 * n || bb >= 2 * n || vs[aa][bb]) continue;
dfs(aa,bb);
}
}
signed main(){
boost;
int t, cnt = 0; cin >> n >> t;
vector<int*>d;
set<int>tt; map<int,int>bb;
for(int i = 0; i < n; i++){
int x,y;
cin >> x >> y;
p.push_back({x,y});
tt.insert(x); tt.insert(y);
}
if(!check()){
cout << "NO";
return 0;
}
for(auto s:tt){
bb[s] = cnt++;
}
for(int i = 0; i < n; i++){
p[i].first = bb[p[i].first];
p[i].second = bb[p[i].second];
grid[p[i].first][p[i].second] = 1;
w[p[i].first][p[i].second] = i;
}
for(int i = 0; i < 2 * n; i++){
for(int j = 0; j < 2 * n; j++){
if(i == 0 || j == 0 || i == 2 * n - 1 || j == 2 * n - 1){
if(!vs[i][j]){
//cout << i << ' ' << j << ' ';
dfs(i,j);
//cout << endl;
}
}
}
}
while(nxt.size()){
vector<pair<int,int>>b;
set<pair<int,int>>s;
b.push_back({nxt[0].first,nxt[0].second});
for(int i = 1; i < nxt.size(); i++){
s.insert({nxt[i].first,nxt[i].second});
//cout << nxt[i].first << ' ' << nxt[i].second << endl;
}
int j = 0;
while(j < b.size()){
for(int k = 0; k < 8; k++){
int nx = b[j].first + x[k], ny = b[j].second + y[k];
if(s.count({nx,ny})){
s.erase({nx,ny});
b.push_back({nx,ny});
ans.push_back(w[nx][ny]);
}
}
j++;
}
ans.push_back(w[nxt[0].first][nxt[0].second]);
//cout << endl;
nxt.clear();
for(int i = 0; i < b.size(); i++){
for(int k = 0; k < 4; k++){
int aa = b[i].first + xx[k], bb = b[i].second + yy[k];
if(aa < 0 || bb < 0 || aa >= 2 * n || bb >= 2 * n || vs[aa][bb]) continue;
if(grid[aa][bb]) {
dfs(aa,bb);
}
}
}
for(int i = 0; i < b.size(); i++){
for(int k = 0; k < 4; k++){
int aa = b[i].first + xx[k], bb = b[i].second + yy[k];
if(aa < 0 || bb < 0 || aa >= 2 * n || bb >= 2 * n || vs[aa][bb]) continue;
dfs(aa,bb);
}
}
}
cout << "YES" << endl;
for(int i = n - 1; i >= 0; i--){
cout << ans[i] + 1 << endl;
}
return 0;
}
Compilation message
skyscrapers.cpp: In function 'bool check()':
skyscrapers.cpp:36:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(j < b.size()){
| ~~^~~~~~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:107:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 1; i < nxt.size(); i++){
| ~~^~~~~~~~~~~~
skyscrapers.cpp:112:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | while(j < b.size()){
| ~~^~~~~~~~~~
skyscrapers.cpp:126:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(int i = 0; i < b.size(); i++){
| ~~^~~~~~~~~~
skyscrapers.cpp:135:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i = 0; i < b.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
340 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Incorrect |
0 ms |
340 KB |
Full cells must be connected |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
340 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Incorrect |
0 ms |
340 KB |
Full cells must be connected |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
340 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Incorrect |
0 ms |
340 KB |
Full cells must be connected |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
ans=NO N=1934 |
| 2 |
Correct |
1 ms |
468 KB |
ans=NO N=1965 |
| 3 |
Runtime error |
578 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
340 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Incorrect |
0 ms |
340 KB |
Full cells must be connected |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
8720 KB |
ans=NO N=66151 |
| 2 |
Correct |
38 ms |
5624 KB |
ans=NO N=64333 |
| 3 |
Runtime error |
628 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
ans=NO N=1934 |
| 2 |
Correct |
1 ms |
468 KB |
ans=NO N=1965 |
| 3 |
Runtime error |
578 ms |
1048576 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
