oj.uz

Submission #207099

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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)