oj.uz

답안 #207099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207099 2020-03-06T13:07:20 Z istlemin Climbers (RMI18_climbers) C++14
0 / 100
 12 ms 7544 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

#define rep(i, a, b) for(ll i = a; i < ll(b); ++i)
#define rrep(i, a, b) for(ll i = b-1; i >= ll(a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

ll n;
vi h;

ll lower(ll s){
    if(h[s]<h[s+1]) return s;
    else return s+1;
}
ll upper(ll s){
    if(h[s]<h[s+1]) return s+1;
    else return s;
}


struct Node {
    ll v,s;

    pair<ll, Node> makeEdge(ll v,Node newNode){
        return {abs(h[v]-h[newNode.v]),newNode};
    }
    
    vector<pair<ll,Node>> edges(){
        vector<pair<ll,Node>> ret;

        if(h[v+1]<h[v]){
            ll mnS = min(h[s],h[s+1]);
            if(mnS>=h[v+1])
                ret.emplace_back(makeEdge(v,Node({lower(s),v})));
            if(mnS<=h[v+1])
                ret.emplace_back(makeEdge(v,Node({v+1,s})));
            if(mnS>=h[v-1])
                ret.emplace_back(makeEdge(v,Node({lower(s),v-1})));
            if(mnS<=h[v-1])
                ret.emplace_back(makeEdge(v,Node({v-1,s})));
        } else {
            ll mxS = max(h[s],h[s+1]);
            if(mxS<=h[v+1])
                ret.emplace_back(makeEdge(v,Node({upper(s),v})));
            if(mxS>=h[v+1])
                ret.emplace_back(makeEdge(v,Node({v+1,s})));
            if(mxS<=h[v-1])
                ret.emplace_back(makeEdge(v,Node({upper(s),v-1})));
            if(mxS>=h[v-1])
                ret.emplace_back(makeEdge(v,Node({v-1,s})));
        }

        if(h[v]==h[s]) {
            ret.emplace_back(makeEdge(v,Node({s,v})));
            ret.emplace_back(makeEdge(v,Node({s,v-1})));
        }
        if(h[v]==h[s+1]) {
            ret.emplace_back(makeEdge(v,Node({s+1,v})));
            ret.emplace_back(makeEdge(v,Node({s+1,v-1})));
        }

        //cout<<v<<" "<<s<<": ";
        //trav(r,ret) cout<<"("<<r.second.v<<","<<r.second.s<<") ";
        //cout<<endl;

        return ret;
    }

    bool invalid(){
        return v==0||v==n-1||s==0||s==n-2;
    }
};

bool operator <(const Node& x, const Node& y) {
    return false;
}


int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);

    cin>>n;
    vi htemp;
    rep(i,0,n) {
        ll x;
        cin>>x;
        if(!htemp.size()||htemp.back()!=x) htemp.push_back(x);
    }
    h.push_back(1e9);
    h.push_back(0);
    rep(i,1,htemp.size()-1){
        if((htemp[i]<htemp[i-1])==(htemp[i]<htemp[i+1])){
            h.push_back(htemp[i]);
        }
    }
    h.push_back(0);
    h.push_back(1e9);

    //trav(hi,h) cout<<hi<<" ";
    //cout<<endl;

    n = h.size();

    set<pair<ll,Node>> q;
    vector<vector<bool>> seen(n,vector<bool>(n));
    q.emplace(0,Node({1,n-3}));
    while(q.size()){
        ll d = q.begin()->first;
        Node V = q.begin()->second;
        q.erase(q.begin());
        if(seen[V.v][V.s]||V.invalid()) continue;
        seen[V.v][V.s] = true;

        //cout<<d<<": "<<V.v<<" "<<V.s<<endl;

        if(V.v==V.s||V.v-1==V.s){
            cout<<d<<endl;
            return 0;
        }
        trav(e,V.edges()){
            q.emplace(d+e.first,e.second);
        }
    }
    assert(false);
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 6 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 8 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 12 ms 7544 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 6 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 8 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 9 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 10 ms 4984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 10 ms 4856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 11 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 12 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 12 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)