oj.uz

Submission #1072653

# Submission time Handle Problem Language Result Execution time Memory
1072653 2024-08-24T01:55:17 Z PenguinsAreCute Building Skyscrapers (CEOI19_skyscrapers) C++17
8 / 100
 93 ms 14032 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> 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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB ans=YES N=1
2 Correct 1 ms 3932 KB ans=YES N=4
3 Correct 1 ms 3928 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 1 ms 3928 KB ans=YES N=9
6 Correct 1 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 1 ms 3964 KB ans=NO N=10
9 Correct 1 ms 3932 KB ans=YES N=10
10 Correct 1 ms 3932 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 1 ms 3932 KB ans=YES N=9
13 Correct 2 ms 3932 KB ans=YES N=9
14 Correct 2 ms 3932 KB ans=YES N=8
15 Correct 2 ms 3764 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB ans=YES N=1
2 Correct 1 ms 3932 KB ans=YES N=4
3 Correct 1 ms 3928 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 1 ms 3928 KB ans=YES N=9
6 Correct 1 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 1 ms 3964 KB ans=NO N=10
9 Correct 1 ms 3932 KB ans=YES N=10
10 Correct 1 ms 3932 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 1 ms 3932 KB ans=YES N=9
13 Correct 2 ms 3932 KB ans=YES N=9
14 Correct 2 ms 3932 KB ans=YES N=8
15 Correct 2 ms 3764 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Incorrect 1 ms 3928 KB Added cell 17 (1,2) not reachable from infinity
18 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB ans=YES N=1
2 Correct 1 ms 3932 KB ans=YES N=4
3 Correct 1 ms 3928 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 1 ms 3928 KB ans=YES N=9
6 Correct 1 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 1 ms 3964 KB ans=NO N=10
9 Correct 1 ms 3932 KB ans=YES N=10
10 Correct 1 ms 3932 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 1 ms 3932 KB ans=YES N=9
13 Correct 2 ms 3932 KB ans=YES N=9
14 Correct 2 ms 3932 KB ans=YES N=8
15 Correct 2 ms 3764 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Incorrect 1 ms 3928 KB Added cell 17 (1,2) not reachable from infinity
18 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB ans=NO N=1934
2 Correct 2 ms 3932 KB ans=NO N=1965
3 Incorrect 4 ms 4184 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 622)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB ans=YES N=1
2 Correct 1 ms 3932 KB ans=YES N=4
3 Correct 1 ms 3928 KB ans=NO N=4
4 Correct 1 ms 3932 KB ans=YES N=5
5 Correct 1 ms 3928 KB ans=YES N=9
6 Correct 1 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 1 ms 3964 KB ans=NO N=10
9 Correct 1 ms 3932 KB ans=YES N=10
10 Correct 1 ms 3932 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 1 ms 3932 KB ans=YES N=9
13 Correct 2 ms 3932 KB ans=YES N=9
14 Correct 2 ms 3932 KB ans=YES N=8
15 Correct 2 ms 3764 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Incorrect 1 ms 3928 KB Added cell 17 (1,2) not reachable from infinity
18 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 12752 KB ans=NO N=66151
2 Correct 61 ms 6516 KB ans=NO N=64333
3 Incorrect 93 ms 14032 KB Added cell 69151 (160,-91) not reachable from infinity
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB ans=NO N=1934
2 Correct 2 ms 3932 KB ans=NO N=1965
3 Incorrect 4 ms 4184 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 622)
4 Halted 0 ms 0 KB -