oj.uz

Submission #1072876

# Submission time Handle Problem Language Result Execution time Memory
1072876 2024-08-24T06:14:29 Z PenguinsAreCute Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 250 ms 19652 KB 
#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

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

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB ans=YES N=1
2 Correct 2 ms 3932 KB ans=YES N=4
3 Correct 2 ms 3932 KB ans=NO N=4
4 Correct 2 ms 3932 KB ans=YES N=5
5 Correct 2 ms 3932 KB ans=YES N=9
6 Correct 3 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 2 ms 3932 KB ans=NO N=10
9 Correct 2 ms 3932 KB ans=YES N=10
10 Correct 2 ms 3928 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 2 ms 3968 KB ans=YES N=9
13 Correct 1 ms 3932 KB ans=YES N=9
14 Correct 1 ms 3932 KB ans=YES N=8
15 Correct 2 ms 3932 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Correct 2 ms 3932 KB ans=YES N=17
18 Correct 2 ms 3860 KB ans=YES N=25
19 Correct 2 ms 3932 KB ans=YES N=100
20 Correct 2 ms 3932 KB ans=YES N=185
21 Correct 2 ms 3932 KB ans=NO N=174
22 Correct 2 ms 3932 KB ans=YES N=90
23 Correct 2 ms 3928 KB ans=YES N=63
24 Correct 2 ms 3932 KB ans=YES N=87
25 Correct 2 ms 3932 KB ans=YES N=183
26 Correct 2 ms 3984 KB ans=YES N=188
27 Correct 2 ms 3932 KB ans=YES N=183
28 Correct 2 ms 3932 KB ans=YES N=189
29 Correct 2 ms 3932 KB ans=YES N=200
30 Correct 2 ms 3932 KB ans=YES N=190
31 Correct 2 ms 3932 KB ans=YES N=187
32 Correct 2 ms 3932 KB ans=YES N=187
33 Correct 2 ms 3932 KB ans=YES N=182
34 Correct 2 ms 3844 KB ans=YES N=184
35 Correct 2 ms 3932 KB ans=YES N=188
36 Correct 2 ms 3932 KB ans=YES N=181
37 Correct 2 ms 3932 KB ans=YES N=188
38 Correct 2 ms 3968 KB ans=YES N=191
39 Correct 2 ms 3932 KB ans=YES N=196
40 Correct 2 ms 3928 KB ans=YES N=196
41 Correct 2 ms 3932 KB ans=YES N=196
42 Correct 2 ms 3932 KB ans=YES N=196
43 Correct 2 ms 3932 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB ans=YES N=1
2 Correct 2 ms 3932 KB ans=YES N=4
3 Correct 2 ms 3932 KB ans=NO N=4
4 Correct 2 ms 3932 KB ans=YES N=5
5 Correct 2 ms 3932 KB ans=YES N=9
6 Correct 3 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 2 ms 3932 KB ans=NO N=10
9 Correct 2 ms 3932 KB ans=YES N=10
10 Correct 2 ms 3928 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 2 ms 3968 KB ans=YES N=9
13 Correct 1 ms 3932 KB ans=YES N=9
14 Correct 1 ms 3932 KB ans=YES N=8
15 Correct 2 ms 3932 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Correct 2 ms 3932 KB ans=YES N=17
18 Correct 2 ms 3860 KB ans=YES N=25
19 Correct 2 ms 3932 KB ans=YES N=100
20 Correct 2 ms 3932 KB ans=YES N=185
21 Correct 2 ms 3932 KB ans=NO N=174
22 Correct 2 ms 3932 KB ans=YES N=90
23 Correct 2 ms 3928 KB ans=YES N=63
24 Correct 2 ms 3932 KB ans=YES N=87
25 Correct 2 ms 3932 KB ans=YES N=183
26 Correct 2 ms 3984 KB ans=YES N=188
27 Correct 2 ms 3932 KB ans=YES N=183
28 Correct 2 ms 3932 KB ans=YES N=189
29 Correct 2 ms 3932 KB ans=YES N=200
30 Correct 2 ms 3932 KB ans=YES N=190
31 Correct 2 ms 3932 KB ans=YES N=187
32 Correct 2 ms 3932 KB ans=YES N=187
33 Correct 2 ms 3932 KB ans=YES N=182
34 Correct 2 ms 3844 KB ans=YES N=184
35 Correct 2 ms 3932 KB ans=YES N=188
36 Correct 2 ms 3932 KB ans=YES N=181
37 Correct 2 ms 3932 KB ans=YES N=188
38 Correct 2 ms 3968 KB ans=YES N=191
39 Correct 2 ms 3932 KB ans=YES N=196
40 Correct 2 ms 3928 KB ans=YES N=196
41 Correct 2 ms 3932 KB ans=YES N=196
42 Correct 2 ms 3932 KB ans=YES N=196
43 Correct 2 ms 3932 KB ans=YES N=195
44 Correct 3 ms 4020 KB ans=NO N=1934
45 Correct 4 ms 3932 KB ans=NO N=1965
46 Correct 4 ms 3928 KB ans=YES N=1824
47 Correct 5 ms 3932 KB ans=YES N=1981
48 Correct 5 ms 3932 KB ans=YES N=1814
49 Correct 3 ms 3932 KB ans=YES N=1854
50 Correct 4 ms 3932 KB ans=YES N=1831
51 Correct 4 ms 4188 KB ans=YES N=2000
52 Correct 4 ms 3932 KB ans=YES N=1847
53 Correct 3 ms 3932 KB ans=YES N=1819
54 Correct 4 ms 4188 KB ans=YES N=1986
55 Correct 3 ms 4072 KB ans=YES N=2000
56 Correct 3 ms 3932 KB ans=YES N=1834
57 Correct 5 ms 3932 KB ans=YES N=1860
58 Correct 3 ms 3944 KB ans=YES N=1898
59 Correct 3 ms 3932 KB ans=YES N=1832
60 Correct 4 ms 4016 KB ans=YES N=1929
61 Correct 4 ms 3932 KB ans=YES N=1919
62 Correct 4 ms 3932 KB ans=YES N=1882
63 Correct 4 ms 3932 KB ans=YES N=1922
64 Correct 4 ms 3928 KB ans=YES N=1989
65 Correct 4 ms 3932 KB ans=YES N=1978
66 Correct 3 ms 3928 KB ans=YES N=1867
67 Correct 4 ms 3972 KB ans=YES N=1942

Subtask #4
0 / 17.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB ans=YES N=1
2 Correct 2 ms 3932 KB ans=YES N=4
3 Correct 2 ms 3932 KB ans=NO N=4
4 Correct 2 ms 3932 KB ans=YES N=5
5 Correct 2 ms 3932 KB ans=YES N=9
6 Correct 3 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 2 ms 3932 KB ans=NO N=10
9 Correct 2 ms 3932 KB ans=YES N=10
10 Correct 2 ms 3928 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 2 ms 3968 KB ans=YES N=9
13 Correct 1 ms 3932 KB ans=YES N=9
14 Correct 1 ms 3932 KB ans=YES N=8
15 Correct 2 ms 3932 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Correct 2 ms 3932 KB ans=YES N=17
18 Correct 2 ms 3860 KB ans=YES N=25
19 Correct 2 ms 3932 KB ans=YES N=100
20 Correct 2 ms 3932 KB ans=YES N=185
21 Correct 2 ms 3932 KB ans=NO N=174
22 Correct 2 ms 3932 KB ans=YES N=90
23 Correct 2 ms 3928 KB ans=YES N=63
24 Correct 2 ms 3932 KB ans=YES N=87
25 Correct 2 ms 3932 KB ans=YES N=183
26 Correct 2 ms 3984 KB ans=YES N=188
27 Correct 2 ms 3932 KB ans=YES N=183
28 Correct 2 ms 3932 KB ans=YES N=189
29 Correct 2 ms 3932 KB ans=YES N=200
30 Correct 2 ms 3932 KB ans=YES N=190
31 Correct 2 ms 3932 KB ans=YES N=187
32 Correct 2 ms 3932 KB ans=YES N=187
33 Correct 2 ms 3932 KB ans=YES N=182
34 Correct 2 ms 3844 KB ans=YES N=184
35 Correct 2 ms 3932 KB ans=YES N=188
36 Correct 2 ms 3932 KB ans=YES N=181
37 Correct 2 ms 3932 KB ans=YES N=188
38 Correct 2 ms 3968 KB ans=YES N=191
39 Correct 2 ms 3932 KB ans=YES N=196
40 Correct 2 ms 3928 KB ans=YES N=196
41 Correct 2 ms 3932 KB ans=YES N=196
42 Correct 2 ms 3932 KB ans=YES N=196
43 Correct 2 ms 3932 KB ans=YES N=195
44 Correct 3 ms 4020 KB ans=NO N=1934
45 Correct 4 ms 3932 KB ans=NO N=1965
46 Correct 4 ms 3928 KB ans=YES N=1824
47 Correct 5 ms 3932 KB ans=YES N=1981
48 Correct 5 ms 3932 KB ans=YES N=1814
49 Correct 3 ms 3932 KB ans=YES N=1854
50 Correct 4 ms 3932 KB ans=YES N=1831
51 Correct 4 ms 4188 KB ans=YES N=2000
52 Correct 4 ms 3932 KB ans=YES N=1847
53 Correct 3 ms 3932 KB ans=YES N=1819
54 Correct 4 ms 4188 KB ans=YES N=1986
55 Correct 3 ms 4072 KB ans=YES N=2000
56 Correct 3 ms 3932 KB ans=YES N=1834
57 Correct 5 ms 3932 KB ans=YES N=1860
58 Correct 3 ms 3944 KB ans=YES N=1898
59 Correct 3 ms 3932 KB ans=YES N=1832
60 Correct 4 ms 4016 KB ans=YES N=1929
61 Correct 4 ms 3932 KB ans=YES N=1919
62 Correct 4 ms 3932 KB ans=YES N=1882
63 Correct 4 ms 3932 KB ans=YES N=1922
64 Correct 4 ms 3928 KB ans=YES N=1989
65 Correct 4 ms 3932 KB ans=YES N=1978
66 Correct 3 ms 3928 KB ans=YES N=1867
67 Correct 4 ms 3972 KB ans=YES N=1942
68 Correct 90 ms 9684 KB ans=NO N=66151
69 Correct 60 ms 6992 KB ans=NO N=64333
70 Correct 106 ms 10248 KB ans=YES N=69316
71 Correct 93 ms 9956 KB ans=YES N=66695
72 Correct 101 ms 10192 KB ans=YES N=68436
73 Correct 102 ms 10296 KB ans=YES N=70000
74 Correct 103 ms 10292 KB ans=YES N=68501
75 Correct 102 ms 10340 KB ans=YES N=70000
76 Correct 91 ms 9932 KB ans=YES N=65009
77 Correct 91 ms 9168 KB ans=YES N=67007
78 Correct 89 ms 8980 KB ans=YES N=66357
79 Correct 102 ms 8928 KB ans=YES N=65430
80 Correct 84 ms 8984 KB ans=YES N=65790
81 Correct 94 ms 8952 KB ans=YES N=66020
82 Correct 101 ms 9184 KB ans=YES N=65809
83 Correct 98 ms 9748 KB ans=YES N=65651
84 Correct 87 ms 9164 KB ans=YES N=68040
85 Correct 90 ms 9164 KB ans=YES N=66570
86 Correct 96 ms 9816 KB ans=YES N=65421
87 Correct 100 ms 10208 KB ans=YES N=68351
88 Correct 100 ms 9944 KB ans=YES N=67027
89 Correct 56 ms 9164 KB ans=YES N=68879
90 Correct 90 ms 9836 KB ans=YES N=67256
91 Correct 237 ms 17360 KB ans=YES N=148315
92 Correct 144 ms 10068 KB ans=NO N=142745
93 Correct 133 ms 10832 KB ans=NO N=148443
94 Correct 248 ms 19160 KB ans=YES N=148328
95 Correct 250 ms 19424 KB ans=YES N=147855
96 Correct 244 ms 19652 KB ans=YES N=150000
97 Correct 227 ms 18884 KB ans=YES N=144725
98 Correct 235 ms 19400 KB ans=YES N=149445
99 Correct 223 ms 18932 KB ans=YES N=144455
100 Correct 232 ms 18644 KB ans=YES N=143487
101 Correct 247 ms 19144 KB ans=YES N=149688
102 Correct 223 ms 16876 KB ans=YES N=141481
103 Correct 188 ms 16844 KB ans=YES N=147430
104 Correct 215 ms 17116 KB ans=YES N=142247
105 Correct 238 ms 17672 KB ans=YES N=149941
106 Correct 187 ms 16588 KB ans=YES N=141635
107 Correct 205 ms 16328 KB ans=YES N=142896
108 Correct 203 ms 16340 KB ans=YES N=142069
109 Correct 227 ms 17612 KB ans=YES N=142378
110 Correct 226 ms 18432 KB ans=YES N=150000
111 Correct 184 ms 16088 KB ans=YES N=141452
112 Correct 166 ms 15572 KB ans=YES N=134453
113 Correct 164 ms 16324 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9680 KB ans=NO N=66151
2 Correct 60 ms 6996 KB ans=NO N=64333
3 Incorrect 98 ms 10216 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 7320)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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