Submission #1029783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029783		c2zi6	Shortcut (IOI16_shortcut)	C++14	71 / 100	2025 ms	3532 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;*/
        rep(i, n) rep(j, n) {
            ll sum = x[i] + x[j];
            ll dif = x[i] - x[j];
            if (mns <= sum && sum <= mxs && 
                mnd <= dif && dif <= mxd) return true;
        }
        return false;
    };

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

• 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