oj.uz

답안 #564652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564652 2022-05-19T12:37:10 Z Majid Building Skyscrapers (CEOI19_skyscrapers) C++17
0 / 100
 336 ms 19144 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<ll, pair<ll, ll> >, vector<pair<ll, pair<ll, ll> > >, greater<pair<ll, pair<ll, ll> > > > pq;
    pq.push({order[vec[0]], vec[0]});
        
    vector<ll> res;
    while(sz(pq)){
    
            ll x = pq.top().s.f, y = pq.top().s.s, pos = pq.top().f;
            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<ll, pair<ll, ll>> qq;
                        qq.s.f = pch.f;
                        qq.s.s = pch.s;
                        qq.f = 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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 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 Incorrect 0 ms 212 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 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 Incorrect 0 ms 212 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 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 Incorrect 0 ms 212 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB ans=NO N=1934
2 Correct 2 ms 596 KB ans=NO N=1965
3 Incorrect 5 ms 724 KB Added cell 1824 (370,234) not reachable from infinity
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 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 Incorrect 0 ms 212 KB Added cell 8 (2,0) not reachable from infinity
11 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 19144 KB ans=NO N=66151
2 Correct 78 ms 10824 KB ans=NO N=64333
3 Incorrect 336 ms 18500 KB Added cell 69316 (-22,-94) not reachable from infinity
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB ans=NO N=1934
2 Correct 2 ms 596 KB ans=NO N=1965
3 Incorrect 5 ms 724 KB Added cell 1824 (370,234) not reachable from infinity
4 Halted 0 ms 0 KB -