Submission #697405

#	Time	Username	Problem	Language	Result	Execution time	Memory
697405		qwerasdfzxcl	Shortcut (IOI16_shortcut)	C++17	23 / 100	2078 ms	340 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 1e17;
struct Square{
    ll lm, um, lp, up;
    ll cx, cy, R;

    Square(){lm = lp = -INF, um = up = INF;}

    void update(ll x, ll y, ll r){
        lm = max(lm, x-y-r);
        um = min(um, x-y+r);
        lp = max(lp, x+y-r);
        up = min(up, x+y+r);
    }
    void update(ll x, ll r, Square &S){
        lm = max(lm, x-r + S.lm);
        um = min(um, x+r + S.um);
        lp = max(lp, x-r + S.lp);
        up = min(up, x+r + S.up);
    }

    bool valid(){return lm <= um && lp <= up;}
    bool info(){
        //printf(" %lld %lld %lld %lld\n", lm, um, lp, up);
        if (lm==-INF) return 0;
        cx =  lm + um + lp + up;
        cy = -lm - um + lp + up;
        R = (um - lm) * 2;
        return 1;
    }
};
struct pq2{
    pair<ll, int> a[2];
    pq2(){a[0] = a[1] = make_pair(INF, 0);}
    void push(ll x, int y){
        auto p = make_pair(x, y);
        if (p < a[1]) swap(p, a[1]);
        if (a[1] < a[0]) swap(a[0], a[1]);
    }
};

int n, I1[1001000], I2[1001000], chk[1001000];
ll X[1001000], a[1001000], c[1001000], d;

bool ok(ll MX){
    //printf("check %lld\n", MX);
    fill(chk, chk+n+1, 0);

    ll mx = -INF;
    vector<int> L, R;

    for (int i=1;i<=n;i++){
        if (mx + X[i] + c[i] > MX) chk[i] |= 2;
        mx = max(mx, - X[i] + c[i]);
    }
    mx = -INF;
    for (int i=n;i;i--){
        if (mx - X[i] + c[i] > MX) chk[i] |= 1;
        if (chk[i]==3) return 0;
        mx = max(mx, X[i] + c[i]);
    }

    for (int i=1;i<=n;i++) if (chk[I1[i]]&1) L.push_back(I1[i]);
    for (int i=1;i<=n;i++) if (chk[I2[i]]&2) R.push_back(I2[i]);

    /*for (auto &x:L) printf("%d ", x);
    printf("\n");
    for (auto &x:R) printf("%d ", x);
    printf("\n");*/

    if (L.empty()) return 1;
    int b = *max_element(L.begin(), L.end());

    assert(!R.empty());
    assert(b < *min_element(R.begin(), R.end()));

    for (auto &i:L) a[i] = c[i] + (X[b] - X[i]);
    for (auto &j:R) a[j] = c[j] + (X[j] - X[b]);

    for (int i=0;i<(int)L.size()-1;i++) assert(a[L[i]] <= a[L[i+1]]);
    for (int i=0;i<(int)R.size()-1;i++) assert(a[R[i]] >= a[R[i+1]]);

    int pt = 0;
    Square s, js;

    for (auto &i:L){
        while(pt<(int)R.size() && a[i] + a[R[pt]] > MX){
            js.update(0, X[R[pt]], -c[R[pt]]);
            pt++;
        }

        s.update(X[i], MX - c[i] - d, js);
        if (!s.valid()) return 0;
    }

    if (!s.info()) return 1;

    pq2 mnX, mnY;
    for (int i=1;i<=n;i++){
        mnX.push((abs(s.cx - X[i] * 4)), i);
        mnY.push((abs(s.cy - X[i] * 4)), i);
    }

    ll val = INF;
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++){
            if (mnX.a[i].second != mnY.a[j].second) val = min(val, mnX.a[i].first + mnY.a[j].first);
        }
    }

    return val <= s.R;
}

bool cmp1(int i, int j){return -X[i]+c[i] < -X[j]+c[j];}
bool cmp2(int i, int j){return X[i]+c[i] > X[j]+c[j];}

ll naive(int N, std::vector<int> L, std::vector<int> D, int C){
    ll ans = INF;
    for (int i=1;i<N;i++) X[i] = X[i-1] + L[i-1];
    for (int i=0;i<N;i++){
        for (int j=i+1;j<N;j++){
            ll mx = *max_element(D.begin(), D.end());
            for (int s=0;s<N;s++){
                for (int e=s+1;e<N;e++){
                    mx = max(mx, min(X[e] - X[s], min(abs(X[j]-X[e]) + abs(X[i]-X[s]) + C, abs(X[j]-X[s]) + abs(X[i] - X[e]) + C)) + D[s] + D[e]);
                }
            }

            ans = min(ans, mx);
        }
    }
    return ans;
}

long long find_shortcut(int N, std::vector<int> L, std::vector<int> D, int C){
    return naive(N, L, D, C);

    n = N;
    for (int i=1;i<=n;i++) c[i] = D[i-1];
    for (int i=2;i<=n;i++) X[i] = X[i-1] + L[i-2];
    d = C;

    for (int i=1;i<=n;i++) I1[i] = i, I2[i] = i;
    sort(I1+1, I1+n+1, cmp1);
    sort(I2+1, I2+n+1, cmp2);

    ll l = *max_element(c+1, c+n+1), r = 1e15 + 100, ans = 1e15 + 100;
    while(l<=r){
        ll mid = (l+r)/2;
        if (ok(mid)) r = mid-1, ans = mid;
        else l = mid+1;
    }

    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3