제출 #1030037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030037		c2zi6	Shortcut (IOI16_shortcut)	C++14	71 / 100	2033 ms	3568 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;
        int l, r;
        l = lower_bound(all(X), verx) - X.begin();
        r = upper_bound(all(X), verx) - 1 - X.begin();
        for (ll y : X) if (vary <= y && y <= very) {
            ll L = max(mnd + y, mns - y);
            ll R = min(mxd + y, mxs - y);
            while (l-1 >= 0 && X[l-1] >= L) l--;
            while (l < X.size() && X[l] < L) l++;
            while (r+1 < X.size() && X[r+1] <= R) r++;
            while (r >= 0 && X[r] > R) r--;
            if (l <= r) 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);
}

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

shortcut.cpp: In lambda function:
shortcut.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             while (l < X.size() && X[l] < L) l++;
      |                    ~~^~~~~~~~~~
shortcut.cpp:86:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while (r+1 < X.size() && X[r+1] <= R) r++;
      |                    ~~~~^~~~~~~~~~

• 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