oj.uz

Submission #564645

# Submission time Handle Problem Language Result Execution time Memory
564645 2022-05-19T12:31:12 Z Majid Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 544 ms 62528 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);
    vector<pair<ll, pair<ll, ll> > > ex(n);
    map<pair<ll, ll>, bool> visited, exist;
    map<pair<ll, ll>, ll> order;
    
    for(ll i = 0; i < n; i++){
        
        cin>>ex[i].s.f>>ex[i].s.s;
        ex[i].f = i+1;
    }
    
    sort(all(ex));
    
    for(ll i = 0; i < n; i++){
        
        vec[i].f = ex[i].s.f;
        vec[i].s = ex[i].s.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 1 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 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 212 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 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 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 1 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 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 212 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 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 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 0 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 212 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 340 KB ans=YES N=190
31 Correct 1 ms 340 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 340 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 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 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 1 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 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 212 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 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 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 0 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 212 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 340 KB ans=YES N=190
31 Correct 1 ms 340 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 340 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 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 2 ms 596 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 4 ms 728 KB ans=YES N=1981
48 Correct 4 ms 724 KB ans=YES N=1814
49 Correct 4 ms 772 KB ans=YES N=1854
50 Correct 5 ms 724 KB ans=YES N=1831
51 Correct 4 ms 724 KB ans=YES N=2000
52 Correct 4 ms 784 KB ans=YES N=1847
53 Correct 4 ms 852 KB ans=YES N=1819
54 Correct 5 ms 704 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 980 KB ans=YES N=1860
58 Correct 4 ms 980 KB ans=YES N=1898
59 Correct 4 ms 852 KB ans=YES N=1832
60 Correct 5 ms 1108 KB ans=YES N=1929
61 Correct 4 ms 852 KB ans=YES N=1919
62 Correct 5 ms 980 KB ans=YES N=1882
63 Correct 5 ms 1108 KB ans=YES N=1922
64 Correct 4 ms 852 KB ans=YES N=1989
65 Correct 4 ms 964 KB ans=YES N=1978
66 Correct 4 ms 872 KB ans=YES N=1867
67 Correct 5 ms 852 KB ans=YES N=1942

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB ans=NO N=1934
2 Correct 2 ms 596 KB ans=NO N=1965
3 Incorrect 4 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 1 ms 212 KB ans=YES N=9
6 Correct 0 ms 212 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 212 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 212 KB ans=YES N=9
14 Correct 0 ms 212 KB ans=YES N=8
15 Correct 0 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 0 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 212 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 340 KB ans=YES N=190
31 Correct 1 ms 340 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 340 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 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 2 ms 596 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 4 ms 728 KB ans=YES N=1981
48 Correct 4 ms 724 KB ans=YES N=1814
49 Correct 4 ms 772 KB ans=YES N=1854
50 Correct 5 ms 724 KB ans=YES N=1831
51 Correct 4 ms 724 KB ans=YES N=2000
52 Correct 4 ms 784 KB ans=YES N=1847
53 Correct 4 ms 852 KB ans=YES N=1819
54 Correct 5 ms 704 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 980 KB ans=YES N=1860
58 Correct 4 ms 980 KB ans=YES N=1898
59 Correct 4 ms 852 KB ans=YES N=1832
60 Correct 5 ms 1108 KB ans=YES N=1929
61 Correct 4 ms 852 KB ans=YES N=1919
62 Correct 5 ms 980 KB ans=YES N=1882
63 Correct 5 ms 1108 KB ans=YES N=1922
64 Correct 4 ms 852 KB ans=YES N=1989
65 Correct 4 ms 964 KB ans=YES N=1978
66 Correct 4 ms 872 KB ans=YES N=1867
67 Correct 5 ms 852 KB ans=YES N=1942
68 Correct 172 ms 18672 KB ans=NO N=66151
69 Correct 67 ms 10760 KB ans=NO N=64333
70 Correct 189 ms 17132 KB ans=YES N=69316
71 Correct 171 ms 16452 KB ans=YES N=66695
72 Correct 188 ms 16940 KB ans=YES N=68436
73 Correct 174 ms 17412 KB ans=YES N=70000
74 Correct 180 ms 17068 KB ans=YES N=68501
75 Correct 174 ms 17640 KB ans=YES N=70000
76 Correct 165 ms 17252 KB ans=YES N=65009
77 Correct 173 ms 21984 KB ans=YES N=67007
78 Correct 179 ms 23816 KB ans=YES N=66357
79 Correct 186 ms 25176 KB ans=YES N=65430
80 Correct 184 ms 24744 KB ans=YES N=65790
81 Correct 189 ms 23620 KB ans=YES N=66020
82 Correct 177 ms 22616 KB ans=YES N=65809
83 Correct 182 ms 18660 KB ans=YES N=65651
84 Correct 199 ms 29376 KB ans=YES N=68040
85 Correct 192 ms 26852 KB ans=YES N=66570
86 Correct 167 ms 16920 KB ans=YES N=65421
87 Correct 175 ms 18112 KB ans=YES N=68351
88 Correct 161 ms 16456 KB ans=YES N=67027
89 Correct 154 ms 21168 KB ans=YES N=68879
90 Correct 180 ms 18104 KB ans=YES N=67256
91 Correct 461 ms 37016 KB ans=YES N=148315
92 Correct 169 ms 23784 KB ans=NO N=142745
93 Correct 176 ms 24668 KB ans=NO N=148443
94 Correct 438 ms 36288 KB ans=YES N=148328
95 Correct 498 ms 36280 KB ans=YES N=147855
96 Correct 459 ms 36668 KB ans=YES N=150000
97 Correct 544 ms 35424 KB ans=YES N=144725
98 Correct 507 ms 36464 KB ans=YES N=149445
99 Correct 467 ms 35444 KB ans=YES N=144455
100 Correct 467 ms 35136 KB ans=YES N=143487
101 Correct 475 ms 36808 KB ans=YES N=149688
102 Correct 484 ms 47184 KB ans=YES N=141481
103 Correct 476 ms 59356 KB ans=YES N=147430
104 Correct 451 ms 41736 KB ans=YES N=142247
105 Correct 506 ms 47136 KB ans=YES N=149941
106 Correct 459 ms 56276 KB ans=YES N=141635
107 Correct 464 ms 53368 KB ans=YES N=142896
108 Correct 500 ms 56780 KB ans=YES N=142069
109 Correct 433 ms 37896 KB ans=YES N=142378
110 Correct 478 ms 50760 KB ans=YES N=150000
111 Correct 457 ms 62420 KB ans=YES N=141452
112 Correct 440 ms 59424 KB ans=YES N=134453
113 Correct 434 ms 62528 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 18604 KB ans=NO N=66151
2 Correct 73 ms 10844 KB ans=NO N=64333
3 Incorrect 214 ms 17100 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 596 KB ans=NO N=1934
2 Correct 2 ms 596 KB ans=NO N=1965
3 Incorrect 4 ms 724 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -