Submission #1072876

#TimeUsernameProblemLanguageResultExecution timeMemory
1072876PenguinsAreCuteBuilding Skyscrapers (CEOI19_skyscrapers)C++17
54 / 100
250 ms19652 KiB
#include <bits/stdc++.h> using namespace std; using i2 = pair<int,int>; using vi = vector<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> perm; bitset<150005> vis; vector<int> adj[150005]; void bfs(int x, vector<int> &r, vector<int> &c) { vis[x]=1; priority_queue<vi,vector<vi>,greater<vi>> pq; for(pq.push({r[x],c[x],x});pq.size();) { int y = pq.top()[2]; pq.pop(); perm.push_back(y); for(auto z: adj[y]) if(!vis[z]) { vis[z]=1; pq.push({r[z],c[z],z}); } } } 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}; 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]) adj[i].push_back((*it).i); } bfs(min_element(all(r))-begin(r),r,c); if(sz(perm)<n) return {-1}; 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); } }

Compilation message (stderr)

skyscrapers.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | 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...