oj.uz

Submission #1072657

# Submission time Handle Problem Language Result Execution time Memory
1072657 2024-08-24T02:00:13 Z kym Building Skyscrapers (CEOI19_skyscrapers) C++14
54 / 100
 354 ms 24516 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int,int>pi;
const int oo = 1'000'000'000'000'000'000ll;
int dx[]={-1,0,1,-1,1,-1,0,1};
int dy[]={-1,-1,-1,0,0,1,1,1};
vector<int>ord;
map<pi,int>idx;
map<pi,bool>done;
int32_t main(){
	int n,t;cin>>n>>t;
	pi mn={oo,oo};
	for(int i=1;i<=n;i++){
		int x,y;cin>>x>>y;
		idx[{x,y}]=i;
		mn=min(mn,make_pair(x,y));
	}
	priority_queue<pi,vector<pi>,greater<pi>>pq;
	pq.push(mn);
	done[mn]=1;
	while(pq.size()){
		pi cur=pq.top();pq.pop();
		int x=cur.first,y=cur.second;
		ord.push_back(idx[{x,y}]);
		for(int k=0;k<8;k++){
			int nx=x+dx[k],ny=y+dy[k];
			if(idx.find({nx,ny}) != idx.end() && !done[{nx,ny}]){
				done[{nx,ny}]=1;
				pq.push({nx,ny});
			}
		}
	}
	if(ord.size() != n)cout<<"NO\n";
	else{
		cout<<"YES\n";
		for(auto x:ord)cout<<x<<"\n";
	}
}

Compilation message

skyscrapers.cpp: In function 'int32_t main()':
skyscrapers.cpp:34:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   34 |  if(ord.size() != n)cout<<"NO\n";
      |     ~~~~~~~~~~~^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB ans=NO N=1934
2 Correct 1 ms 348 KB ans=NO N=1965
3 Incorrect 3 ms 604 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 0 ms 344 KB ans=YES N=1
2 Correct 0 ms 348 KB ans=YES N=4
3 Correct 0 ms 348 KB ans=NO N=4
4 Correct 0 ms 348 KB ans=YES N=5
5 Correct 0 ms 348 KB ans=YES N=9
6 Correct 0 ms 348 KB ans=YES N=5
7 Correct 0 ms 348 KB ans=NO N=9
8 Correct 0 ms 348 KB ans=NO N=10
9 Correct 0 ms 348 KB ans=YES N=10
10 Correct 0 ms 348 KB ans=YES N=10
11 Correct 1 ms 348 KB ans=YES N=10
12 Correct 1 ms 600 KB ans=YES N=9
13 Correct 0 ms 348 KB ans=YES N=9
14 Correct 0 ms 348 KB ans=YES N=8
15 Correct 0 ms 348 KB ans=YES N=8
16 Correct 0 ms 348 KB ans=NO N=2
17 Correct 0 ms 348 KB ans=YES N=17
18 Correct 0 ms 348 KB ans=YES N=25
19 Correct 1 ms 348 KB ans=YES N=100
20 Correct 1 ms 348 KB ans=YES N=185
21 Correct 1 ms 348 KB ans=NO N=174
22 Correct 1 ms 348 KB ans=YES N=90
23 Correct 0 ms 348 KB ans=YES N=63
24 Correct 1 ms 348 KB ans=YES N=87
25 Correct 0 ms 348 KB ans=YES N=183
26 Correct 1 ms 348 KB ans=YES N=188
27 Correct 0 ms 436 KB ans=YES N=183
28 Correct 1 ms 344 KB ans=YES N=189
29 Correct 1 ms 348 KB ans=YES N=200
30 Correct 1 ms 344 KB ans=YES N=190
31 Correct 1 ms 348 KB ans=YES N=187
32 Correct 1 ms 348 KB ans=YES N=187
33 Correct 1 ms 348 KB ans=YES N=182
34 Correct 1 ms 348 KB ans=YES N=184
35 Correct 1 ms 348 KB ans=YES N=188
36 Correct 1 ms 344 KB ans=YES N=181
37 Correct 0 ms 348 KB ans=YES N=188
38 Correct 1 ms 348 KB ans=YES N=191
39 Correct 0 ms 348 KB ans=YES N=196
40 Correct 1 ms 348 KB ans=YES N=196
41 Correct 0 ms 348 KB ans=YES N=196
42 Correct 1 ms 344 KB ans=YES N=196
43 Correct 0 ms 348 KB ans=YES N=195
44 Correct 2 ms 344 KB ans=NO N=1934
45 Correct 2 ms 348 KB ans=NO N=1965
46 Correct 4 ms 604 KB ans=YES N=1824
47 Correct 4 ms 600 KB ans=YES N=1981
48 Correct 3 ms 604 KB ans=YES N=1814
49 Correct 3 ms 604 KB ans=YES N=1854
50 Correct 3 ms 604 KB ans=YES N=1831
51 Correct 6 ms 600 KB ans=YES N=2000
52 Correct 3 ms 604 KB ans=YES N=1847
53 Correct 3 ms 660 KB ans=YES N=1819
54 Correct 3 ms 600 KB ans=YES N=1986
55 Correct 3 ms 604 KB ans=YES N=2000
56 Correct 3 ms 604 KB ans=YES N=1834
57 Correct 3 ms 604 KB ans=YES N=1860
58 Correct 3 ms 604 KB ans=YES N=1898
59 Correct 3 ms 604 KB ans=YES N=1832
60 Correct 3 ms 716 KB ans=YES N=1929
61 Correct 3 ms 604 KB ans=YES N=1919
62 Correct 3 ms 604 KB ans=YES N=1882
63 Correct 3 ms 604 KB ans=YES N=1922
64 Correct 3 ms 700 KB ans=YES N=1989
65 Correct 2 ms 604 KB ans=YES N=1978
66 Correct 3 ms 604 KB ans=YES N=1867
67 Correct 3 ms 604 KB ans=YES N=1942
68 Correct 94 ms 10188 KB ans=NO N=66151
69 Correct 44 ms 4948 KB ans=NO N=64333
70 Correct 120 ms 10444 KB ans=YES N=69316
71 Correct 121 ms 10128 KB ans=YES N=66695
72 Correct 115 ms 10436 KB ans=YES N=68436
73 Correct 115 ms 10692 KB ans=YES N=70000
74 Correct 121 ms 10384 KB ans=YES N=68501
75 Correct 115 ms 10696 KB ans=YES N=70000
76 Correct 99 ms 9928 KB ans=YES N=65009
77 Correct 104 ms 10188 KB ans=YES N=67007
78 Correct 97 ms 10188 KB ans=YES N=66357
79 Correct 92 ms 9928 KB ans=YES N=65430
80 Correct 93 ms 10188 KB ans=YES N=65790
81 Correct 93 ms 10184 KB ans=YES N=66020
82 Correct 90 ms 10060 KB ans=YES N=65809
83 Correct 106 ms 10188 KB ans=YES N=65651
84 Correct 103 ms 10432 KB ans=YES N=68040
85 Correct 97 ms 10188 KB ans=YES N=66570
86 Correct 104 ms 9932 KB ans=YES N=65421
87 Correct 102 ms 10440 KB ans=YES N=68351
88 Correct 127 ms 10264 KB ans=YES N=67027
89 Correct 88 ms 10528 KB ans=YES N=68879
90 Correct 111 ms 10268 KB ans=YES N=67256
91 Correct 266 ms 22204 KB ans=YES N=148315
92 Correct 90 ms 10560 KB ans=NO N=142745
93 Correct 124 ms 12728 KB ans=NO N=148443
94 Correct 302 ms 23956 KB ans=YES N=148328
95 Correct 297 ms 23936 KB ans=YES N=147855
96 Correct 305 ms 24516 KB ans=YES N=150000
97 Correct 315 ms 23488 KB ans=YES N=144725
98 Correct 324 ms 24252 KB ans=YES N=149445
99 Correct 317 ms 23484 KB ans=YES N=144455
100 Correct 314 ms 23236 KB ans=YES N=143487
101 Correct 354 ms 24084 KB ans=YES N=149688
102 Correct 263 ms 22960 KB ans=YES N=141481
103 Correct 256 ms 23992 KB ans=YES N=147430
104 Correct 270 ms 23232 KB ans=YES N=142247
105 Correct 291 ms 24344 KB ans=YES N=149941
106 Correct 251 ms 23164 KB ans=YES N=141635
107 Correct 253 ms 22976 KB ans=YES N=142896
108 Correct 251 ms 22972 KB ans=YES N=142069
109 Correct 256 ms 22432 KB ans=YES N=142378
110 Correct 273 ms 24256 KB ans=YES N=150000
111 Correct 234 ms 22840 KB ans=YES N=141452
112 Correct 213 ms 21612 KB ans=YES N=134453
113 Correct 275 ms 23220 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 9672 KB ans=NO N=66151
2 Correct 37 ms 4328 KB ans=NO N=64333
3 Incorrect 115 ms 9928 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 2 ms 348 KB ans=NO N=1934
2 Correct 1 ms 348 KB ans=NO N=1965
3 Incorrect 3 ms 604 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -