oj.uz

Submission #1072764

# Submission time Handle Problem Language Result Execution time Memory
1072764 2024-08-24T04:16:02 Z PenguinsAreCute Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 1277 ms 35816 KB 
#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

skyscrapers.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main() {
      | ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ans=YES N=1
2 Correct 1 ms 4088 KB ans=YES N=4
3 Correct 1 ms 3932 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 2 ms 5980 KB ans=YES N=9
6 Incorrect 1 ms 3932 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ans=YES N=1
2 Correct 1 ms 4088 KB ans=YES N=4
3 Correct 1 ms 3932 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 2 ms 5980 KB ans=YES N=9
6 Incorrect 1 ms 3932 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ans=YES N=1
2 Correct 1 ms 4088 KB ans=YES N=4
3 Correct 1 ms 3932 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 2 ms 5980 KB ans=YES N=9
6 Incorrect 1 ms 3932 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7060 KB ans=NO N=1934
2 Correct 6 ms 4760 KB ans=NO N=1965
3 Incorrect 7 ms 4444 KB Full cells must be connected
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB ans=YES N=1
2 Correct 1 ms 4088 KB ans=YES N=4
3 Correct 1 ms 3932 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 2 ms 5980 KB ans=YES N=9
6 Incorrect 1 ms 3932 KB Unexpected end of file - int32 expected
7 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 24824 KB ans=NO N=66151
2 Correct 157 ms 35816 KB ans=NO N=64333
3 Incorrect 1277 ms 15292 KB Full cells must be connected
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7060 KB ans=NO N=1934
2 Correct 6 ms 4760 KB ans=NO N=1965
3 Incorrect 7 ms 4444 KB Full cells must be connected
4 Halted 0 ms 0 KB -