Submission #697394

#	Time	Username	Problem	Language	Result	Execution time	Memory
697394		qwerasdfzxcl	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	360 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;}
    void info(){
        //printf(" %lld %lld %lld %lld\n", lm, um, lp, up);
        cx =  lm + um + lp + up;
        cy = -lm - um + lp + up;
        R = (um - lm) * 2;
    }
};

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[n]-X[i]) + c[i] > MX) chk[i] |= 2;
        mx = max(mx, X[n] - 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]);

    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;
    }

    s.info();

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

    return mnX + mnY <= 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];}

long long find_shortcut(int N, std::vector<int> L, std::vector<int> D, int 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 = 0, 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: 0 / 9
• Subtask 2: 0 / 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