제출 #241980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241980		lyc	Shortcut (IOI16_shortcut)	C++14	0 / 100	5 ms	384 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using ll=long long;

const int mxN = 1e6+5;
const ll mxX = 1e17;

int N, C, D[mxN];
ll X[mxN];
int id1[mxN], id2[mxN];

bool check(ll k) {
    array<ll,4> res = {-mxX,mxX,-mxX,mxX}, cur;
    FOR(J,1,N){
        ll mxs = -mxX, mne = mxX;
        FOR(I,1,J-1){
            if (D[I]+D[J]+(X[J]-X[I]) <= k) continue;
            mxs = max(mxs,X[I]-(k-C-D[I]));
            mne = min(mne,X[I]+(k-C-D[I]));
        }
        if (mxs > mne) return 0;
        ll a = mxs+D[J], b = mne-D[J];
        //TRACE(J _ a _ b);
        cur = {X[J]+a,X[J]+b,X[J]-b,X[J]-a};
        res[0] = max(res[0],cur[0]);
        res[1] = min(res[1],cur[1]);
        res[2] = max(res[2],cur[2]);
        res[3] = min(res[3],cur[3]);
        //TRACE(cur[0] _ cur[1] _ cur[2] _ cur[3]);
        //TRACE(res[0] _ res[1] _ res[2] _ res[3]);
        if (res[0] > res[1] || res[2] > res[3]) return 0;
    }
    return 1;
}

ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    N = n, C = c;
    X[1] = 0;
    FOR(i,2,N) X[i] = X[i-1] + l[i-2];
    int mx = 0, smx = 0;
    FOR(i,1,N){
        D[i] = d[i-1];
        int tmp = D[i];
        if (tmp > mx) swap(tmp,mx);
        if (tmp > smx) swap(tmp,smx);
    }

    FOR(i,1,N) id1[i] = id2[i] = i;
    sort(id1+1,id1+1+N,[](int a, int b){
            ll p = X[a]-D[a], q = X[b]-D[b];
            return (p == q ? a < b : p < q);
            });
    sort(id2+1,id2+1+N,[](int a, int b){
            ll p = X[a]+D[a], q = X[b]+D[b];
            return (p == q ? a < b : p < q);
            });
    ll lo = mx+smx-1, hi = mxX;
    while (hi-lo > 1){ 
        ll mid = (lo+hi)/2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }
    return hi;
}

• 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