oj.uz

답안 #336748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336748 2020-12-16T17:01:38 Z Sorting Climbers (RMI18_climbers) C++17
5 / 100
 112 ms 215788 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 5000 + 3;
const ll INF = 1e18;

void build_edges(int pos1, int pos2, bool exact, vector<array<ll, 4>> &adj);

int n, a[N];
ll dist[N][N][2];

ll dijkstra(int pos1, int pos2, bool exact){
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;

    for(int pos1 = 0; pos1 < n; ++pos1)
        for(int pos2 = pos1; pos2 < n; ++pos2)
            for(int exact = 0; exact <= 1; ++exact)
                dist[pos1][pos2][exact] = INF;

    dist[pos1][pos2][exact] = 0;
    pq.push({0, pos1, pos2, exact});

    vector<array<ll, 4>> adj;
    while(!pq.empty()){
        auto [d, pos1, pos2, exact] = pq.top();
        pq.pop();

        if(d != dist[pos1][pos2][exact]) continue;
        if(pos1 == pos2) return d;

        adj.clear();
        build_edges(pos1, pos2, exact, adj);
        for(auto [pos1_to, pos2_to, exact_to, cost]: adj){
            ll cand = d + cost;
            if(cand < dist[pos1_to][pos2_to][exact_to]){
                dist[pos1_to][pos2_to][exact_to] = cand;
                pq.push({cand, pos1_to, pos2_to, exact_to});
            } 
        }
    }

    return INF;
}

void move_dp(int mv1, int mv2, int pos1, int pos2, bool exact, int x, vector<array<ll, 4>> &adj){
    //cout << mv1 << " " << mv2 << " " << pos1 << " " << pos2 << " " << exact <<  " " << x << endl;
    if(a[mv1] > x && x > a[mv2]) return;
    if(a[mv1] < x && x < a[mv2]) return;

    int new_x;
    if(a[mv1] < x) new_x = max(a[mv1], a[mv2]);
    else new_x = min(a[mv1], a[mv2]);

    int new_exact = (a[mv1] == new_x) ? 0 : 1;
    
    int new_pos1 = (a[mv1] == new_x) ? mv1 : pos1;
    int new_pos2 = (a[mv2] == new_x) ? mv2 : pos2;
    if(a[pos1] == x && a[mv1] != new_x){
        if(mv1 == pos1 + 1) new_pos1 = pos1;
        else new_pos1 = pos1 - 1;
    }
    if(a[pos2] == x && a[mv2] != new_x){
        if(mv2 == pos2 - 1) new_pos2 = pos2;
        else new_pos2 = pos2 + 1;
    }

    adj.push_back({new_pos1, new_pos2, new_exact, abs(x - new_x)});
    
    //cout << pos1 << " " << pos2 << " " << exact << " -> " << new_pos1 << " " << new_pos2 << " " << new_exact << " " << abs(x - new_x) << endl;
}

void build_edges(int pos1, int pos2, bool exact, vector<array<ll, 4>> &adj){
    int x = !exact ? a[pos1] : a[pos2];
    bool e1 = (x == a[pos1]), e2 = (x == a[pos2]);
    vector<int> v1, v2;

    if(e1){
        v1.push_back(pos1 + 1);
        if(pos1) v1.push_back(pos1 - 1);
    }
    else{
        v1.push_back(pos1 + 1);
        v1.push_back(pos1);
    }

    if(e2){
        v2.push_back(pos2 - 1);
        if(pos2 != n - 1) v2.push_back(pos2 + 1);
    }
    else{
        v2.push_back(pos2 - 1);
        v2.push_back(pos2);
    }

    move_dp(v1[0], v2[0], pos1, pos2, exact, x, adj);
    if(v2.size() == 2) move_dp(v1[0], v2[1], pos1, pos2, exact, x, adj);
    if(v1.size() == 2) move_dp(v1[1], v2[0], pos1, pos2, exact, x, adj);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];

    vector<int> v;
    v.push_back(a[0]);

    for(int i = 1; i < n - 1; ++i){
        if(v.back() <= a[i] && a[i] <= a[i + 1])
            continue;
        if(v.back() >= a[i] && a[i] >= a[i + 1])
            continue;
        v.push_back(a[i]);
    }
    v.push_back(a[n - 1]);

    if(v.size() == 2 && v[0] == v[1])
        v.pop_back();

    n = v.size();
    for(int i = 0; i < n; ++i)
        a[i] = v[i];

    //build_edges(0, n - 1, 0);
    ll ans = dijkstra(0, n - 1, 0);

    if(ans == INF) cout << "NO\n";
    else cout << ans << "\n";
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 876 KB Output isn't correct
2 Incorrect 1 ms 2284 KB Output isn't correct
3 Incorrect 7 ms 12140 KB Output isn't correct
4 Incorrect 44 ms 82924 KB Output isn't correct
5 Incorrect 112 ms 215788 KB Output isn't correct

Subtask #2
5.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Incorrect 1 ms 620 KB Output isn't correct
3 Incorrect 1 ms 1132 KB Output isn't correct
4 Incorrect 1 ms 748 KB Output isn't correct
5 Incorrect 2 ms 3180 KB Output isn't correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 748 KB Output isn't correct
2 Incorrect 2 ms 2156 KB Output isn't correct
3 Incorrect 7 ms 11500 KB Output isn't correct
4 Incorrect 40 ms 76268 KB Output isn't correct
5 Incorrect 40 ms 75628 KB Output isn't correct
6 Incorrect 73 ms 137964 KB Output isn't correct
7 Incorrect 69 ms 130412 KB Output isn't correct
8 Incorrect 106 ms 195436 KB Output isn't correct
9 Incorrect 106 ms 199148 KB Output isn't correct
10 Incorrect 110 ms 194668 KB Output isn't correct