제출 #1030034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030034		c2zi6	Shortcut (IOI16_shortcut)	C++14	71 / 100	2081 ms	3732 KiB

shortcut

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "shortcut.h"

ll solve(int n, VL l, VL d, ll C) {
    VL X(n);
    X[0] = 0;
    replr(i, 1, n-1) X[i] = X[i-1] + l[i-1];
    auto can = [&](ll k) {
        ll mxs, mns, mxd, mnd;
        mxs = mxd = +1e18;
        mns = mnd = -1e18;
        replr(i, 0, n-1) replr(j, i+1, n-1) {
            if (d[i] + d[j] + X[j] - X[i] <= k) continue;
            ll a = X[i];
            ll b = X[j];
            ll c = k-C-d[i]-d[j];
            if (c < 0) return false;
            /*cout << "PAIR (" << i << ", " << j << ")" << endl;*/
            /*cout << "   " << a + b - c << " <= sum <= " << a + b + c << endl;*/
            /*cout << "   " << a - b - c << " <= dif <= " << a - b + c << endl;*/
            /*cout << "   polygon("*/
            /*    "(" << (a+b-c+a-b+c)/2 << ", " << (a+b-c-a+b-c)/2 << "),"*/
            /*    "(" << (a+b+c+a-b+c)/2 << ", " << (a+b+c-a+b-c)/2 << "),"*/
            /*    "(" << (a+b+c+a-b-c)/2 << ", " << (a+b+c-a+b+c)/2 << "),"*/
            /*    "(" << (a+b-c+a-b-c)/2 << ", " << (a+b-c-a+b+c)/2 << "))"*/
            /*    << endl;*/
            /*cout << "   " << d[i] + d[j] + x[j] - x[i] << " <= " << k << endl;*/
            /*cout << endl;*/
            setmax(mns, a + b - c);
            setmin(mxs, a + b + c);
            setmax(mnd, a - b - c);
            setmin(mxd, a - b + c);
        }
        /*cout << "INTERSECTION: " << endl;*/
        /*cout << "   " << mns << " <= sum <= " << mxs << endl;*/
        /*cout << "   " << mnd << " <= dif <= " << mxd << endl;*/
        /*cout << "polygon("*/
        /*    "(" << (mns+mxd)/2 << ", " << (mns-mxd)/2 << "),"*/
        /*    "(" << (mxs+mxd)/2 << ", " << (mxs-mxd)/2 << "),"*/
        /*    "(" << (mxs+mnd)/2 << ", " << (mxs-mnd)/2 << "),"*/
        /*    "(" << (mns+mnd)/2 << ", " << (mns-mnd)/2 << "))"*/
        /*    << endl;*/
        /*cout << endl;*/
        ll verx, very, vary;
        verx = (mxs+mnd)/2;
        very = (mxs-mnd)/2;
        vary = (mns-mxd)/2;
        /*cout << vary << " <= y <= " << very << endl;*/
        for (ll y : X) if (vary <= y && y <= very) {
            ll l = max(mnd + y, mns - y);
            ll r = min(mxd + y, mxs - y);
            /*cout << "line: y = " << y << endl;*/
            /*cout << "   x range: " << l << ".." << r << endl;*/
            for (ll x : X) if (l <= x && x <= r) return true;
        }
        return false;
    };
    /*return can(100);*/
    /*replr(i, 1, 200) {*/
    /*    cout << i << ": " << can(i) << endl;*/
    /*}*/
    ll L = 0, R = 1e18;
    while (L + 1 < R) {
        ll m = (L + R) / 2;
        if (can(m)) R = m;
        else L = m;
    }
    return R;
}

ll find_shortcut(int n, VI l, VI d, int c) {
    VL L, D;
    rep(i, n) L.pb(l[i]), D.pb(d[i]);
    return solve(n, L, D, c);
}

컴파일 시 표준 에러 (stderr) 메시지

shortcut.cpp: In lambda function:
shortcut.cpp:74:12: warning: variable 'verx' set but not used [-Wunused-but-set-variable]
   74 |         ll verx, very, vary;
      |            ^~~~

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