oj.uz

Submission #1072820

# Submission time Handle Problem Language Result Execution time Memory
1072820 2024-08-24T05:34:24 Z PenguinsAreCute Building Skyscrapers (CEOI19_skyscrapers) C++17
22 / 100
 3500 ms 113552 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())

namespace ufds {
  int par[1200005], sz[1200005], spec;
  vector<int> child[1200005]; // "literally a child"
  vector<int> toUp;
  void init(int _spec) {
    iota(par,par+1200005,0);
    fill(sz,sz+1200005,0);
    for(int i=0;i<1200005;i++) child[i]={i};
    spec = _spec;
    toUp = {spec};
  }
  int onion(int x) {return par[x]=(par[x]==x?x:onion(par[x]));}
  void unite(int x, int y) {
    x = onion(x); y = onion(y);
    if(sz[x]>sz[y]) swap(x,y);
    if(x==y) return;
    if(x==onion(spec)) for(auto i: child[y]) toUp.push_back(i);
    if(y==onion(spec)) for(auto i: child[x]) toUp.push_back(i);
    for(auto i: child[x]) child[y].push_back(i);
    sz[y]+=sz[x]; par[x]=y;
  }
}

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).i;
}
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]);
    vacant.push_back({r[i]+dx[j],c[i]+dy[j]});
    vadj[i].push_back(x);
    if(j<4) eadj[i].push_back(x);
  }
  sort(all(vacant));
  vacant.resize(unique(all(vacant))-begin(vacant));
  int lft = min_element(all(r))-begin(r);
  int st = find(all(vacant),vector<int>{r[lft]-1,c[lft]})-begin(vacant);
  ufds::init(st);
  vector<bool> on(sz(vacant),0); on[st]=1;
  auto turnOn = [&vacant,&on](int x) {
    on[x]=1;
    for(int i=0;i<4;i++) {
      auto it = find(all(vacant),vector<int>{vacant[x][0]+dx[i],vacant[x][1]+dy[i]});
      if(it==end(vacant)) continue;
      if(!on[it-begin(vacant)]) continue;
      ufds::unite(it-begin(vacant),x);
    }
  };
  for(int i=0;i<sz(vacant);i++) if(val(n,vacant[i][0],vacant[i][1])==-1) turnOn(i);

  fill(dist,dist+n,-1);
  bfs(0);
  if(*min_element(dist,dist+n)==-1) return {-1};

  vector<bool> used(n);
  priority_queue<i2> pq;
  auto pushOne = [&pq,&used,n](int x, int y) {
    for(int i=0;i<4;i++) {
      int z = val(n,x+dx[i],y+dy[i]);
      if(z==-1) continue;
      if(used[z]) continue;
      pq.push({dist[z],z});
      used[z]=1;
    }
  };
  auto push = [&pq,&pushOne,&vacant]() {
    for(auto i: ufds::toUp) pushOne(vacant[i][0],vacant[i][1]);
    ufds::toUp.clear();
  };
  push();

  vector<int> perm;
  while(pq.size()) {
    int x = pq.top().second; pq.pop();
    perm.push_back(x);
    auto it = find(all(vacant),vector<int>{r[x],c[x]});
    if(it!=end(vacant)) turnOn(it-begin(vacant));
    push();
  }
  reverse(perm.begin(),perm.end());
  if(perm.size()<n) {cout<<"F*CK\n"; exit(0);}
  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);
  }
}

/*
g.kd.
.#.m.
f.0.i
j#..b
helca
*/

Compilation message

skyscrapers.cpp: In function 'std::vector<int> build_skyscrapers(int, std::vector<int>, std::vector<int>)':
skyscrapers.cpp:126:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  126 |   if(perm.size()<n) {cout<<"F*CK\n"; exit(0);}
      |      ~~~~~~~~~~~^~
skyscrapers.cpp: At global scope:
skyscrapers.cpp:131:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  131 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 79076 KB ans=YES N=1
2 Correct 58 ms 78928 KB ans=YES N=4
3 Correct 92 ms 78920 KB ans=NO N=4
4 Correct 60 ms 79032 KB ans=YES N=5
5 Correct 71 ms 78932 KB ans=YES N=9
6 Correct 66 ms 78916 KB ans=YES N=5
7 Correct 74 ms 79104 KB ans=NO N=9
8 Correct 90 ms 78896 KB ans=NO N=10
9 Correct 94 ms 79048 KB ans=YES N=10
10 Correct 55 ms 78992 KB ans=YES N=10
11 Correct 56 ms 78868 KB ans=YES N=10
12 Correct 60 ms 78972 KB ans=YES N=9
13 Correct 59 ms 78944 KB ans=YES N=9
14 Correct 57 ms 78928 KB ans=YES N=8
15 Correct 81 ms 79060 KB ans=YES N=8
16 Correct 53 ms 78864 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 79076 KB ans=YES N=1
2 Correct 58 ms 78928 KB ans=YES N=4
3 Correct 92 ms 78920 KB ans=NO N=4
4 Correct 60 ms 79032 KB ans=YES N=5
5 Correct 71 ms 78932 KB ans=YES N=9
6 Correct 66 ms 78916 KB ans=YES N=5
7 Correct 74 ms 79104 KB ans=NO N=9
8 Correct 90 ms 78896 KB ans=NO N=10
9 Correct 94 ms 79048 KB ans=YES N=10
10 Correct 55 ms 78992 KB ans=YES N=10
11 Correct 56 ms 78868 KB ans=YES N=10
12 Correct 60 ms 78972 KB ans=YES N=9
13 Correct 59 ms 78944 KB ans=YES N=9
14 Correct 57 ms 78928 KB ans=YES N=8
15 Correct 81 ms 79060 KB ans=YES N=8
16 Correct 53 ms 78864 KB ans=NO N=2
17 Correct 79 ms 78896 KB ans=YES N=17
18 Correct 76 ms 78928 KB ans=YES N=25
19 Correct 80 ms 79216 KB ans=YES N=100
20 Correct 90 ms 79372 KB ans=YES N=185
21 Correct 70 ms 79136 KB ans=NO N=174
22 Correct 67 ms 79212 KB ans=YES N=90
23 Correct 103 ms 79128 KB ans=YES N=63
24 Correct 83 ms 79128 KB ans=YES N=87
25 Correct 71 ms 79304 KB ans=YES N=183
26 Correct 104 ms 79276 KB ans=YES N=188
27 Correct 68 ms 79452 KB ans=YES N=183
28 Correct 71 ms 79184 KB ans=YES N=189
29 Correct 65 ms 79440 KB ans=YES N=200
30 Correct 84 ms 79664 KB ans=YES N=190
31 Correct 66 ms 79188 KB ans=YES N=187
32 Correct 69 ms 79536 KB ans=YES N=187
33 Correct 82 ms 79672 KB ans=YES N=182
34 Correct 102 ms 79668 KB ans=YES N=184
35 Correct 68 ms 79952 KB ans=YES N=188
36 Correct 66 ms 79700 KB ans=YES N=181
37 Correct 65 ms 79908 KB ans=YES N=188
38 Correct 78 ms 80152 KB ans=YES N=191
39 Correct 65 ms 79440 KB ans=YES N=196
40 Correct 67 ms 79444 KB ans=YES N=196
41 Correct 65 ms 79440 KB ans=YES N=196
42 Correct 64 ms 79532 KB ans=YES N=196
43 Correct 67 ms 79696 KB ans=YES N=195

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 79076 KB ans=YES N=1
2 Correct 58 ms 78928 KB ans=YES N=4
3 Correct 92 ms 78920 KB ans=NO N=4
4 Correct 60 ms 79032 KB ans=YES N=5
5 Correct 71 ms 78932 KB ans=YES N=9
6 Correct 66 ms 78916 KB ans=YES N=5
7 Correct 74 ms 79104 KB ans=NO N=9
8 Correct 90 ms 78896 KB ans=NO N=10
9 Correct 94 ms 79048 KB ans=YES N=10
10 Correct 55 ms 78992 KB ans=YES N=10
11 Correct 56 ms 78868 KB ans=YES N=10
12 Correct 60 ms 78972 KB ans=YES N=9
13 Correct 59 ms 78944 KB ans=YES N=9
14 Correct 57 ms 78928 KB ans=YES N=8
15 Correct 81 ms 79060 KB ans=YES N=8
16 Correct 53 ms 78864 KB ans=NO N=2
17 Correct 79 ms 78896 KB ans=YES N=17
18 Correct 76 ms 78928 KB ans=YES N=25
19 Correct 80 ms 79216 KB ans=YES N=100
20 Correct 90 ms 79372 KB ans=YES N=185
21 Correct 70 ms 79136 KB ans=NO N=174
22 Correct 67 ms 79212 KB ans=YES N=90
23 Correct 103 ms 79128 KB ans=YES N=63
24 Correct 83 ms 79128 KB ans=YES N=87
25 Correct 71 ms 79304 KB ans=YES N=183
26 Correct 104 ms 79276 KB ans=YES N=188
27 Correct 68 ms 79452 KB ans=YES N=183
28 Correct 71 ms 79184 KB ans=YES N=189
29 Correct 65 ms 79440 KB ans=YES N=200
30 Correct 84 ms 79664 KB ans=YES N=190
31 Correct 66 ms 79188 KB ans=YES N=187
32 Correct 69 ms 79536 KB ans=YES N=187
33 Correct 82 ms 79672 KB ans=YES N=182
34 Correct 102 ms 79668 KB ans=YES N=184
35 Correct 68 ms 79952 KB ans=YES N=188
36 Correct 66 ms 79700 KB ans=YES N=181
37 Correct 65 ms 79908 KB ans=YES N=188
38 Correct 78 ms 80152 KB ans=YES N=191
39 Correct 65 ms 79440 KB ans=YES N=196
40 Correct 67 ms 79444 KB ans=YES N=196
41 Correct 65 ms 79440 KB ans=YES N=196
42 Correct 64 ms 79532 KB ans=YES N=196
43 Correct 67 ms 79696 KB ans=YES N=195
44 Correct 2857 ms 80300 KB ans=NO N=1934
45 Correct 257 ms 105876 KB ans=NO N=1965
46 Correct 111 ms 91536 KB ans=YES N=1824
47 Correct 131 ms 94252 KB ans=YES N=1981
48 Correct 111 ms 91280 KB ans=YES N=1814
49 Correct 165 ms 96144 KB ans=YES N=1854
50 Correct 115 ms 92300 KB ans=YES N=1831
51 Correct 135 ms 95616 KB ans=YES N=2000
52 Correct 164 ms 98744 KB ans=YES N=1847
53 Correct 202 ms 101260 KB ans=YES N=1819
54 Correct 124 ms 94092 KB ans=YES N=1986
55 Incorrect 317 ms 113552 KB Full cells must be connected
56 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2975 ms 80432 KB ans=NO N=1934
2 Correct 261 ms 105648 KB ans=NO N=1965
3 Incorrect 118 ms 91536 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1049)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 79076 KB ans=YES N=1
2 Correct 58 ms 78928 KB ans=YES N=4
3 Correct 92 ms 78920 KB ans=NO N=4
4 Correct 60 ms 79032 KB ans=YES N=5
5 Correct 71 ms 78932 KB ans=YES N=9
6 Correct 66 ms 78916 KB ans=YES N=5
7 Correct 74 ms 79104 KB ans=NO N=9
8 Correct 90 ms 78896 KB ans=NO N=10
9 Correct 94 ms 79048 KB ans=YES N=10
10 Correct 55 ms 78992 KB ans=YES N=10
11 Correct 56 ms 78868 KB ans=YES N=10
12 Correct 60 ms 78972 KB ans=YES N=9
13 Correct 59 ms 78944 KB ans=YES N=9
14 Correct 57 ms 78928 KB ans=YES N=8
15 Correct 81 ms 79060 KB ans=YES N=8
16 Correct 53 ms 78864 KB ans=NO N=2
17 Correct 79 ms 78896 KB ans=YES N=17
18 Correct 76 ms 78928 KB ans=YES N=25
19 Correct 80 ms 79216 KB ans=YES N=100
20 Correct 90 ms 79372 KB ans=YES N=185
21 Correct 70 ms 79136 KB ans=NO N=174
22 Correct 67 ms 79212 KB ans=YES N=90
23 Correct 103 ms 79128 KB ans=YES N=63
24 Correct 83 ms 79128 KB ans=YES N=87
25 Correct 71 ms 79304 KB ans=YES N=183
26 Correct 104 ms 79276 KB ans=YES N=188
27 Correct 68 ms 79452 KB ans=YES N=183
28 Correct 71 ms 79184 KB ans=YES N=189
29 Correct 65 ms 79440 KB ans=YES N=200
30 Correct 84 ms 79664 KB ans=YES N=190
31 Correct 66 ms 79188 KB ans=YES N=187
32 Correct 69 ms 79536 KB ans=YES N=187
33 Correct 82 ms 79672 KB ans=YES N=182
34 Correct 102 ms 79668 KB ans=YES N=184
35 Correct 68 ms 79952 KB ans=YES N=188
36 Correct 66 ms 79700 KB ans=YES N=181
37 Correct 65 ms 79908 KB ans=YES N=188
38 Correct 78 ms 80152 KB ans=YES N=191
39 Correct 65 ms 79440 KB ans=YES N=196
40 Correct 67 ms 79444 KB ans=YES N=196
41 Correct 65 ms 79440 KB ans=YES N=196
42 Correct 64 ms 79532 KB ans=YES N=196
43 Correct 67 ms 79696 KB ans=YES N=195
44 Correct 2857 ms 80300 KB ans=NO N=1934
45 Correct 257 ms 105876 KB ans=NO N=1965
46 Correct 111 ms 91536 KB ans=YES N=1824
47 Correct 131 ms 94252 KB ans=YES N=1981
48 Correct 111 ms 91280 KB ans=YES N=1814
49 Correct 165 ms 96144 KB ans=YES N=1854
50 Correct 115 ms 92300 KB ans=YES N=1831
51 Correct 135 ms 95616 KB ans=YES N=2000
52 Correct 164 ms 98744 KB ans=YES N=1847
53 Correct 202 ms 101260 KB ans=YES N=1819
54 Correct 124 ms 94092 KB ans=YES N=1986
55 Incorrect 317 ms 113552 KB Full cells must be connected
56 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3532 ms 104916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2975 ms 80432 KB ans=NO N=1934
2 Correct 261 ms 105648 KB ans=NO N=1965
3 Incorrect 118 ms 91536 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1049)
4 Halted 0 ms 0 KB -