This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using i2 = pair<int,int>;
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(v) begin(v),end(v)
#define sz(v) int(v.size())
vector<int> vadj[150005];
int dist[150005];
void bfs(int s) {
queue<int> q;
dist[s]=0;
for(q.push(s);q.size();) {
int x = q.front(); q.pop();
for(auto i: vadj[x]) if(dist[i]==-1) {
dist[i]=dist[x]+1;
q.push(i);
}
}
}
struct block {int x, y, i;};
vector<int> build_skyscrapers(int t, vector<int> r, vector<int> c) {
int n = r.size();
block lst[n];
for(int i=0;i<n;i++) lst[i]={r[i],c[i],i};
auto lamb = [](block a, block b){return i2(a.x,a.y)<i2(b.x,b.y);};
sort(lst,lst+n,lamb);
int dx[8]={-1,-1,-1,0,0,1,1,1}, dy[8]={-1,0,1,-1,1,-1,0,1};
vector<int> eadj[n]; int edeg[n]; fill(edeg,edeg+n,0);
for(int i=0;i<n;i++) for(int j=0;j<8;j++) {
auto it=lb(lst,lst+n,block{r[i]+dx[j],c[i]+dy[j],0},lamb);
if(it!=lst+n&&(*it).x==r[i]+dx[j]&&(*it).y==c[i]+dy[j]) {
vadj[i].push_back((*it).i);
if(i==1||i==3||i==4||i==6) eadj[i].push_back((*it).i), edeg[i]++;
}
}
fill(dist,dist+n,-1);
bfs(0);
if(*min_element(dist,dist+n)==-1) return {-1};
priority_queue<i2> pq;
for(int i=0;i<n;i++) if(edeg[i]<4) pq.push({dist[i],i});
vector<int> perm;
while(pq.size()) {
int x = pq.top().second; pq.pop();
perm.push_back(x);
for(auto i: eadj[x]) if(edeg[i]==4) {
edeg[i]=3;
pq.push({dist[i],i});
}
}
reverse(perm.begin(),perm.end());
return perm;
}
// grader
main() {
int n, t;
assert(2==scanf("%d %d",&n,&t));
vector<int> r(n), c(n);
for(int i=0;i<n;i++) assert(2==scanf("%d %d",&r[i],&c[i]));
vector<int> v = build_skyscrapers(t,r,c);
if(v[0]==-1) printf("NO");
else {
printf("YES\n");
for(auto i: v) printf("%d\n",i+1);
}
}
/*
Find node furthest away?
furthest node may be in center.
Find skyscraper edge furthest away among all exposed skyscrapers.
remove it.
repeat.
(furthest from arbitrary node)
*/
Compilation message (stderr)
skyscrapers.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
58 | main() {
| ^~~~
# | 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... |