oj.uz

Submission #564639

# Submission time Handle Problem Language Result Execution time Memory
564639 2022-05-19T12:23:52 Z Majid Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 467 ms 60068 KB 
#include<bits/stdc++.h>
using namespace std;
 
//Types
using ll = long long;
using db = double;
 
//Vectors
#define pb push_back
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(), vec.end()
 
//things
#define f first
#define s second
const int SMALLINF = 1e9 + 7;
const ll BIGINF = ((ll)1e18) + 7;
#define Speeed ios::sync_with_stdio(0);cin.tie(NULL); cout.tie(NULL);

ll dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
ll dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};

// struct info{
// 
//     ll x, y, pos;
// };

void solve(){

    ll n, t;
    cin>>n>>t;
    
    vector<pair<ll, ll> > vec(n);
    map<pair<ll, ll>, bool> visited, exist;
    map<pair<ll, ll>, ll> order;
    
    for(ll i = 0; i < n; i++){
        
        cin>>vec[i].f>>vec[i].s;
        
        pair<ll, ll> p;
        p.f = vec[i].f;
        p.s = vec[i].s;

        exist[p] = true;
        order[p] = i+1;
    }
    
    sort(all(vec));
    visited[vec[0]] = true;
    
    priority_queue<pair<pair<ll, ll>, ll>, vector<pair<pair<ll, ll>, ll> >, greater<pair<pair<ll, ll>, ll> > > pq;
    pq.push({vec[0], order[vec[0]]});
        
    vector<ll> res;
    while(sz(pq)){
    
            ll x = pq.top().f.f, y = pq.top().f.s, pos = pq.top().s;
            pq.pop();
    
            for(ll i = 0; i < 8; i++){
    
                pair<ll, ll> pch;
                pch.f = x+dx[i], pch.s = y+dy[i];
    
                if(exist[pch] and !visited[pch]){
    
                        visited[pch] = true;
                        pair<pair<ll, ll>, ll> qq;
                        qq.f.f = pch.f;
                        qq.f.s = pch.s;
                        qq.s = order[pch];
    
                        pq.push(qq); 
                    }
                }
                res.pb(pos);
            }
    
    if(sz(res)==n){
    
        cout<<"YES\n";
        for(ll i = 0; i < sz(res); i++){
    
            cout<<res[i]<<" ";
        }
    }
    
    else cout<<"NO\n";
}


int main(){
	Speeed
	
    ll t=1;
    // cin>>t;
    
    while(t--){
        
        solve();
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 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 0 ms 212 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 1 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ans=YES N=1
2 Correct 0 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 0 ms 212 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 1 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 1 ms 340 KB ans=YES N=100
20 Correct 1 ms 340 KB ans=YES N=185
21 Correct 1 ms 340 KB ans=NO N=174
22 Correct 1 ms 340 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 340 KB ans=YES N=183
26 Correct 1 ms 340 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 320 KB ans=YES N=190
31 Correct 1 ms 340 KB ans=YES N=187
32 Correct 1 ms 316 KB ans=YES N=187
33 Correct 1 ms 340 KB ans=YES N=182
34 Correct 1 ms 320 KB ans=YES N=184
35 Correct 1 ms 340 KB ans=YES N=188
36 Correct 1 ms 340 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 320 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 0 ms 212 KB ans=YES N=1
2 Correct 0 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 0 ms 212 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 1 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 1 ms 340 KB ans=YES N=100
20 Correct 1 ms 340 KB ans=YES N=185
21 Correct 1 ms 340 KB ans=NO N=174
22 Correct 1 ms 340 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 340 KB ans=YES N=183
26 Correct 1 ms 340 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 320 KB ans=YES N=190
31 Correct 1 ms 340 KB ans=YES N=187
32 Correct 1 ms 316 KB ans=YES N=187
33 Correct 1 ms 340 KB ans=YES N=182
34 Correct 1 ms 320 KB ans=YES N=184
35 Correct 1 ms 340 KB ans=YES N=188
36 Correct 1 ms 340 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 320 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 2 ms 588 KB ans=NO N=1934
45 Correct 2 ms 596 KB ans=NO N=1965
46 Correct 4 ms 724 KB ans=YES N=1824
47 Correct 6 ms 764 KB ans=YES N=1981
48 Correct 5 ms 724 KB ans=YES N=1814
49 Correct 4 ms 724 KB ans=YES N=1854
50 Correct 6 ms 724 KB ans=YES N=1831
51 Correct 4 ms 724 KB ans=YES N=2000
52 Correct 5 ms 852 KB ans=YES N=1847
53 Correct 4 ms 844 KB ans=YES N=1819
54 Correct 5 ms 724 KB ans=YES N=1986
55 Correct 5 ms 980 KB ans=YES N=2000
56 Correct 4 ms 980 KB ans=YES N=1834
57 Correct 5 ms 940 KB ans=YES N=1860
58 Correct 6 ms 984 KB ans=YES N=1898
59 Correct 6 ms 844 KB ans=YES N=1832
60 Correct 6 ms 1088 KB ans=YES N=1929
61 Correct 4 ms 852 KB ans=YES N=1919
62 Correct 6 ms 968 KB ans=YES N=1882
63 Correct 5 ms 1048 KB ans=YES N=1922
64 Correct 4 ms 848 KB ans=YES N=1989
65 Correct 4 ms 852 KB ans=YES N=1978
66 Correct 4 ms 852 KB ans=YES N=1867
67 Correct 7 ms 964 KB ans=YES N=1942

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB ans=NO N=1934
2 Correct 2 ms 592 KB ans=NO N=1965
3 Incorrect 5 ms 724 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 212 KB ans=YES N=1
2 Correct 0 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 0 ms 212 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 1 ms 212 KB ans=NO N=10
9 Correct 0 ms 212 KB ans=YES N=10
10 Correct 0 ms 212 KB ans=YES N=10
11 Correct 1 ms 212 KB ans=YES N=10
12 Correct 1 ms 212 KB ans=YES N=9
13 Correct 1 ms 212 KB ans=YES N=9
14 Correct 1 ms 212 KB ans=YES N=8
15 Correct 1 ms 212 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 1 ms 212 KB ans=YES N=17
18 Correct 1 ms 212 KB ans=YES N=25
19 Correct 1 ms 340 KB ans=YES N=100
20 Correct 1 ms 340 KB ans=YES N=185
21 Correct 1 ms 340 KB ans=NO N=174
22 Correct 1 ms 340 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 340 KB ans=YES N=183
26 Correct 1 ms 340 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 320 KB ans=YES N=190
31 Correct 1 ms 340 KB ans=YES N=187
32 Correct 1 ms 316 KB ans=YES N=187
33 Correct 1 ms 340 KB ans=YES N=182
34 Correct 1 ms 320 KB ans=YES N=184
35 Correct 1 ms 340 KB ans=YES N=188
36 Correct 1 ms 340 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 320 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 2 ms 588 KB ans=NO N=1934
45 Correct 2 ms 596 KB ans=NO N=1965
46 Correct 4 ms 724 KB ans=YES N=1824
47 Correct 6 ms 764 KB ans=YES N=1981
48 Correct 5 ms 724 KB ans=YES N=1814
49 Correct 4 ms 724 KB ans=YES N=1854
50 Correct 6 ms 724 KB ans=YES N=1831
51 Correct 4 ms 724 KB ans=YES N=2000
52 Correct 5 ms 852 KB ans=YES N=1847
53 Correct 4 ms 844 KB ans=YES N=1819
54 Correct 5 ms 724 KB ans=YES N=1986
55 Correct 5 ms 980 KB ans=YES N=2000
56 Correct 4 ms 980 KB ans=YES N=1834
57 Correct 5 ms 940 KB ans=YES N=1860
58 Correct 6 ms 984 KB ans=YES N=1898
59 Correct 6 ms 844 KB ans=YES N=1832
60 Correct 6 ms 1088 KB ans=YES N=1929
61 Correct 4 ms 852 KB ans=YES N=1919
62 Correct 6 ms 968 KB ans=YES N=1882
63 Correct 5 ms 1048 KB ans=YES N=1922
64 Correct 4 ms 848 KB ans=YES N=1989
65 Correct 4 ms 852 KB ans=YES N=1978
66 Correct 4 ms 852 KB ans=YES N=1867
67 Correct 7 ms 964 KB ans=YES N=1942
68 Correct 177 ms 17156 KB ans=NO N=66151
69 Correct 65 ms 9860 KB ans=NO N=64333
70 Correct 186 ms 15976 KB ans=YES N=69316
71 Correct 179 ms 15420 KB ans=YES N=66695
72 Correct 185 ms 15900 KB ans=YES N=68436
73 Correct 192 ms 16252 KB ans=YES N=70000
74 Correct 194 ms 16068 KB ans=YES N=68501
75 Correct 180 ms 16564 KB ans=YES N=70000
76 Correct 172 ms 16292 KB ans=YES N=65009
77 Correct 185 ms 20952 KB ans=YES N=67007
78 Correct 191 ms 22816 KB ans=YES N=66357
79 Correct 210 ms 24232 KB ans=YES N=65430
80 Correct 206 ms 23676 KB ans=YES N=65790
81 Correct 196 ms 22684 KB ans=YES N=66020
82 Correct 190 ms 21556 KB ans=YES N=65809
83 Correct 178 ms 17732 KB ans=YES N=65651
84 Correct 247 ms 28340 KB ans=YES N=68040
85 Correct 199 ms 26016 KB ans=YES N=66570
86 Correct 168 ms 15804 KB ans=YES N=65421
87 Correct 175 ms 17124 KB ans=YES N=68351
88 Correct 173 ms 15424 KB ans=YES N=67027
89 Correct 166 ms 20304 KB ans=YES N=68879
90 Correct 180 ms 17096 KB ans=YES N=67256
91 Correct 432 ms 34132 KB ans=YES N=148315
92 Correct 170 ms 21064 KB ans=NO N=142745
93 Correct 188 ms 22236 KB ans=NO N=148443
94 Correct 440 ms 33728 KB ans=YES N=148328
95 Correct 439 ms 33680 KB ans=YES N=147855
96 Correct 450 ms 34424 KB ans=YES N=150000
97 Correct 427 ms 33096 KB ans=YES N=144725
98 Correct 453 ms 33980 KB ans=YES N=149445
99 Correct 450 ms 33128 KB ans=YES N=144455
100 Correct 427 ms 32728 KB ans=YES N=143487
101 Correct 440 ms 34156 KB ans=YES N=149688
102 Correct 431 ms 44936 KB ans=YES N=141481
103 Correct 462 ms 56868 KB ans=YES N=147430
104 Correct 414 ms 39488 KB ans=YES N=142247
105 Correct 453 ms 44796 KB ans=YES N=149941
106 Correct 441 ms 53848 KB ans=YES N=141635
107 Correct 450 ms 50492 KB ans=YES N=142896
108 Correct 456 ms 54072 KB ans=YES N=142069
109 Correct 419 ms 35116 KB ans=YES N=142378
110 Correct 459 ms 48396 KB ans=YES N=150000
111 Correct 467 ms 59872 KB ans=YES N=141452
112 Correct 420 ms 56728 KB ans=YES N=134453
113 Correct 411 ms 60068 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 17156 KB ans=NO N=66151
2 Correct 64 ms 9328 KB ans=NO N=64333
3 Incorrect 182 ms 16044 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 468 KB ans=NO N=1934
2 Correct 2 ms 592 KB ans=NO N=1965
3 Incorrect 5 ms 724 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -