oj.uz

Submission #798491

# Submission time Handle Problem Language Result Execution time Memory
798491 2023-07-30T18:38:58 Z Ronin13 Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 269 ms 42440 KB 
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <bitset>

#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define mp make_pair

using namespace std;

const ll mod = 998244353;

vector <int> d;



int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int type; cin >> type;
    set <pair<pii, int> > st;
    vector <int> ans;
    pii mn = mp(1e9 + 1, 1e9 + 1);
    int mni;
    map <pii, int> m;
    int x[n + 1], y[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        m[mp(x[i], y[i])] = i; 
        if(mn > mp(x[i], y[i]))
            mn = mp(x[i], y[i]), mni = i;
    }
    st.insert(mp(mn, mni));
    m[mn] = 0;
    d.pb(-1); d.pb(0); d.pb(1);
    while(!st.empty()){
        int x = st.begin()->s;
        pii o = st.begin()->f;
        st.erase(st.begin());
        ans.pb(x);
        for(int i = 0; i < 3; i++){
            int curx = o.f, cury = o.s;
            for(int j = 0; j < 3; j++){
                int nx = curx + d[i];
                int ny = cury + d[j];
                if(m[mp(nx, ny)]){
                    st.insert(mp(mp(nx, ny), m[mp(nx, ny)])), m[mp(nx, ny)] = 0;
                }
            }
        }
    }
    if(ans.size() == n){
        cout << "YES\n";
        for(int i = 0; i < ans.size(); ++i){
            cout << ans[i] << ' ';
        }
    }
    else cout << "NO\n";
    return 0;
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:63:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     if(ans.size() == n){
      |        ~~~~~~~~~~~^~~~
skyscrapers.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 0; i < ans.size(); ++i){
      |                        ~~^~~~~~~~~~~~
skyscrapers.cpp:44:25: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     st.insert(mp(mn, mni));
      |                         ^

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB ans=NO N=1934
2 Correct 1 ms 468 KB ans=NO N=1965
3 Incorrect 2 ms 460 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 1 ms 212 KB ans=YES N=1
2 Correct 1 ms 212 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 212 KB ans=YES N=5
5 Correct 0 ms 212 KB ans=YES N=9
6 Correct 1 ms 360 KB ans=YES N=5
7 Correct 0 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 320 KB ans=YES N=10
11 Correct 0 ms 212 KB ans=YES N=10
12 Correct 0 ms 212 KB ans=YES N=9
13 Correct 0 ms 320 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 ms 324 KB ans=YES N=8
16 Correct 0 ms 212 KB ans=NO N=2
17 Correct 0 ms 212 KB ans=YES N=17
18 Correct 0 ms 212 KB ans=YES N=25
19 Correct 1 ms 340 KB ans=YES N=100
20 Correct 1 ms 328 KB ans=YES N=185
21 Correct 0 ms 212 KB ans=NO N=174
22 Correct 1 ms 212 KB ans=YES N=90
23 Correct 0 ms 340 KB ans=YES N=63
24 Correct 1 ms 328 KB ans=YES N=87
25 Correct 1 ms 340 KB ans=YES N=183
26 Correct 1 ms 320 KB ans=YES N=188
27 Correct 1 ms 340 KB ans=YES N=183
28 Correct 1 ms 340 KB ans=YES N=189
29 Correct 1 ms 340 KB ans=YES N=200
30 Correct 1 ms 340 KB ans=YES N=190
31 Correct 1 ms 328 KB ans=YES N=187
32 Correct 1 ms 340 KB ans=YES N=187
33 Correct 1 ms 340 KB ans=YES N=182
34 Correct 1 ms 328 KB ans=YES N=184
35 Correct 1 ms 340 KB ans=YES N=188
36 Correct 1 ms 324 KB ans=YES N=181
37 Correct 1 ms 340 KB ans=YES N=188
38 Correct 1 ms 340 KB ans=YES N=191
39 Correct 1 ms 340 KB ans=YES N=196
40 Correct 1 ms 340 KB ans=YES N=196
41 Correct 1 ms 340 KB ans=YES N=196
42 Correct 1 ms 340 KB ans=YES N=196
43 Correct 1 ms 340 KB ans=YES N=195
44 Correct 1 ms 460 KB ans=NO N=1934
45 Correct 1 ms 460 KB ans=NO N=1965
46 Correct 2 ms 468 KB ans=YES N=1824
47 Correct 3 ms 456 KB ans=YES N=1981
48 Correct 2 ms 468 KB ans=YES N=1814
49 Correct 2 ms 468 KB ans=YES N=1854
50 Correct 2 ms 460 KB ans=YES N=1831
51 Correct 3 ms 468 KB ans=YES N=2000
52 Correct 2 ms 596 KB ans=YES N=1847
53 Correct 3 ms 596 KB ans=YES N=1819
54 Correct 2 ms 468 KB ans=YES N=1986
55 Correct 3 ms 724 KB ans=YES N=2000
56 Correct 4 ms 764 KB ans=YES N=1834
57 Correct 3 ms 724 KB ans=YES N=1860
58 Correct 3 ms 724 KB ans=YES N=1898
59 Correct 3 ms 596 KB ans=YES N=1832
60 Correct 3 ms 852 KB ans=YES N=1929
61 Correct 2 ms 468 KB ans=YES N=1919
62 Correct 3 ms 720 KB ans=YES N=1882
63 Correct 3 ms 856 KB ans=YES N=1922
64 Correct 2 ms 596 KB ans=YES N=1989
65 Correct 3 ms 596 KB ans=YES N=1978
66 Correct 3 ms 656 KB ans=YES N=1867
67 Correct 3 ms 596 KB ans=YES N=1942
68 Correct 82 ms 8260 KB ans=NO N=66151
69 Correct 25 ms 5300 KB ans=NO N=64333
70 Correct 80 ms 6516 KB ans=YES N=69316
71 Correct 81 ms 6340 KB ans=YES N=66695
72 Correct 79 ms 6512 KB ans=YES N=68436
73 Correct 82 ms 6612 KB ans=YES N=70000
74 Correct 90 ms 6864 KB ans=YES N=68501
75 Correct 82 ms 7024 KB ans=YES N=70000
76 Correct 80 ms 7304 KB ans=YES N=65009
77 Correct 94 ms 11792 KB ans=YES N=67007
78 Correct 100 ms 13680 KB ans=YES N=66357
79 Correct 103 ms 15260 KB ans=YES N=65430
80 Correct 104 ms 14524 KB ans=YES N=65790
81 Correct 102 ms 13508 KB ans=YES N=66020
82 Correct 96 ms 12488 KB ans=YES N=65809
83 Correct 88 ms 8616 KB ans=YES N=65651
84 Correct 133 ms 18980 KB ans=YES N=68040
85 Correct 108 ms 16696 KB ans=YES N=66570
86 Correct 77 ms 6776 KB ans=YES N=65421
87 Correct 82 ms 7748 KB ans=YES N=68351
88 Correct 75 ms 6376 KB ans=YES N=67027
89 Correct 85 ms 10816 KB ans=YES N=68879
90 Correct 82 ms 7784 KB ans=YES N=67256
91 Correct 190 ms 14188 KB ans=YES N=148315
92 Correct 60 ms 11472 KB ans=NO N=142745
93 Correct 72 ms 13760 KB ans=NO N=148443
94 Correct 205 ms 15340 KB ans=YES N=148328
95 Correct 195 ms 15492 KB ans=YES N=147855
96 Correct 195 ms 15708 KB ans=YES N=150000
97 Correct 186 ms 15168 KB ans=YES N=144725
98 Correct 225 ms 15648 KB ans=YES N=149445
99 Correct 204 ms 15388 KB ans=YES N=144455
100 Correct 187 ms 15140 KB ans=YES N=143487
101 Correct 213 ms 15680 KB ans=YES N=149688
102 Correct 231 ms 27432 KB ans=YES N=141481
103 Correct 269 ms 38632 KB ans=YES N=147430
104 Correct 214 ms 21928 KB ans=YES N=142247
105 Correct 262 ms 26300 KB ans=YES N=149941
106 Correct 250 ms 36320 KB ans=YES N=141635
107 Correct 255 ms 32956 KB ans=YES N=142896
108 Correct 268 ms 36652 KB ans=YES N=142069
109 Correct 190 ms 17140 KB ans=YES N=142378
110 Correct 236 ms 29760 KB ans=YES N=150000
111 Correct 262 ms 42440 KB ans=YES N=141452
112 Correct 255 ms 40384 KB ans=YES N=134453
113 Correct 261 ms 42256 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8320 KB ans=NO N=66151
2 Correct 25 ms 5244 KB ans=NO N=64333
3 Incorrect 80 ms 6604 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 1 ms 468 KB ans=NO N=1934
2 Correct 1 ms 468 KB ans=NO N=1965
3 Incorrect 2 ms 460 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -