Submission #1284114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284114		Johann	Shortcut (IOI16_shortcut)	C++20	71 / 100	2097 ms	2372 KiB

shortcut

#include "shortcut.h"

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

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<vi> vvi;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;

#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)

bool possible(int n, ll K, vi &X, vi &D, ll c)
{
    // Is it possible to have a shortcut from y to z.
    vi ineq(4, 1LL << 60); // (-1)^b_1 y + (-1)^b_0 z <= ineq[b_1 b_0], where y < z is a shortcut from continous points y and z
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (D[i] + D[j] + X[j] - X[i] <= K)
                continue;
            ineq[0] = min(ineq[0], K - c - D[i] - D[j] + X[i] + X[j]);
            ineq[1] = min(ineq[1], K - c - D[i] - D[j] + X[i] - X[j]);
            ineq[2] = min(ineq[2], K - c - D[i] - D[j] - X[i] + X[j]);
            ineq[3] = min(ineq[3], K - c - D[i] - D[j] - X[i] - X[j]);
        }
    }

    bool poss = false;
    for (int i = 0; i < n && !poss; ++i)
    {
        for (int j = i + 1; j < n && !poss; ++j)
        {
            poss = true;
            for (int cnt = 0; cnt < 4; ++cnt)
            {
                ll coeff_i = (cnt & 2) ? -1 : 1;
                ll coeff_j = (cnt & 1) ? -1 : 1;
                poss = poss && ((coeff_i * X[i] + coeff_j * X[j]) <= ineq[cnt]);
            }
        }
    }

    return poss;
}

long long find_shortcut(int n, std::vector<int> _l, std::vector<int> _d, int _c)
{
    vi D(all(_d));
    vi L(all(_l));
    ll C = _c;
    vi X(n);
    partial_sum(all(L), X.begin() + 1);

    ll max_diam = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            max_diam = max(max_diam, D[i] + D[j] + X[j] - X[i]);
        }
    }

    ll lo = 0, up = max_diam;
    while (lo < up)
    {
        ll m = (lo + up) / 2;
        if (possible(n, m, X, D, C))
            up = m;
        else
            lo = m + 1;
    }

    return lo;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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