Submission #421659

#	Time	Username	Problem	Language	Result	Execution time	Memory
421659		KoD	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	292 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"

template <class T>
using Vec = std::vector<T>;
using ll = long long;

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

template <class T>
void setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
    }
}

template <class T>
void setmax(T& lhs, const T& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
    }
}

ll find_shortcut(int n, Vec<int> l, Vec<int> d, int c) {
    Vec<ll> x(n);
    for (int i = 1; i < n; ++i) {
        x[i] = x[i - 1] + l[i - 1];
    }
    const auto check = [&](const ll threshold) -> bool {
        ll sum_min = -INF, sum_max = INF;
        ll dif_min = -INF, dif_max = INF;
        for (int i = 0; i < n; ++i) {
            if (d[i] > threshold) {
                return false;
            }
            for (int j = i + 1; j < n; ++j) {
                if (d[i] + d[j] + (x[j] - x[i]) > threshold) {
                    if (d[i] + d[j] + c > threshold) {
                        return false;
                    }
                    setmin(sum_max, (x[i] - d[i]) + (x[j] - d[j]) + threshold - c);
                    setmax(sum_min, (x[i] + d[i]) + (x[j] + d[j]) + c - threshold);
                    setmin(dif_max, -(x[i] + d[i]) + (x[j] - d[j]) + threshold - c);
                    setmax(dif_min, -(x[i] - d[i]) + (x[j] + d[j]) + c - threshold);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (sum_min <= x[i] + x[j] and x[i] + x[j] <= sum_max and dif_min <= x[j] - x[i] and x[i] - x[j] <= dif_max) {
                    return true;
                }
            }
        }
        return false;
    };
    ll ok = INF, ng = 0;
    while (ok - ng > 1) {
        const auto md = (ok + ng) / 2;
        (check(md) ? ok : ng) = md;
    }
    return ok;
}

• 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