Submission #1072653

#TimeUsernameProblemLanguageResultExecution timeMemory
1072653PenguinsAreCuteBuilding Skyscrapers (CEOI19_skyscrapers)C++17
8 / 100
93 ms14032 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> perm; bitset<150005> vis; vector<int> adj[150005]; void dfs(int x) { perm.push_back(x); vis[x]=1; for(auto i: adj[x]) if(!vis[i]) dfs(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}; 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); } dfs(min_element(all(r))-begin(r)); 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:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | 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...