Submission #1072764

#TimeUsernameProblemLanguageResultExecution timeMemory
1072764PenguinsAreCuteBuilding Skyscrapers (CEOI19_skyscrapers)C++17
0 / 100
1277 ms35816 KiB
#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;}; auto lamb = [](block a, block b){return i2(a.x,a.y)<i2(b.x,b.y);}; block lst[150005]; int val(int n, int x, int y) { auto it = lower_bound(lst,lst+n,block{x,y,0},lamb); if(it==lst+n||(*it).x!=x||(*it).y!=y) return -1; return it-lst; } int dx[8]={1,0,-1,0,1,1,-1,-1}; int dy[8]={0,1,0,-1,-1,1,-1,1}; void dfs(int x, vector<vector<int>> &vac) { vac[x].push_back(-1); for(int i=0;i<4;i++) { auto it = lower_bound(vac.begin(),vac.end(),vector<int>{vac[x][0]+dx[i],vac[x][1]+dy[i]}); if(it==vac.end()) continue; if((*it)!=vector<int>{vac[x][0]+dx[i],vac[x][1]+dy[i]}) continue; dfs(it-vac.begin(),vac); } } vector<int> build_skyscrapers(int t, vector<int> r, vector<int> c) { int n = r.size(); for(int i=0;i<n;i++) lst[i]={r[i],c[i],i}; sort(lst,lst+n,lamb); vector<int> eadj[n]; vector<vector<int>> vacant; for(int i=0;i<n;i++) for(int j=0;j<8;j++) { int x = val(n,r[i]+dx[j],c[i]+dy[j]); if(x==-1) { vacant.push_back({r[i]+dx[j],c[i]+dy[j]}); continue; } vadj[i].push_back(x); if(j<4) eadj[i].push_back(x); } sort(vacant.begin(),vacant.end()); int lft = min_element(all(r))-begin(r); int st = lb(all(vacant),vector<int>{r[lft]-1,c[lft]})-begin(vacant); dfs(st,vacant); fill(dist,dist+n,-1); bfs(0); if(*min_element(dist,dist+n)==-1) return {-1}; bool used[n]; fill(used,used+n,0); priority_queue<i2> pq; for(int i=0;i<n;i++) { bool ok = 0; for(int j=0;j<4;j++) if(find(all(vacant),vector<int>{r[i]+dx[j],c[i]+dy[j],-1})!=end(vacant)) ok=1; if(ok) used[i]=1,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(!used[i]) { used[i]=1; 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:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...