제출 #915276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915276		vjudge1	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	440 KiB

shortcut

#include "shortcut.h"

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

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
        vector<int64_t> a(n), b(n);  // a = x + d, b = x - d
        vector<int64_t> x(n);
        for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
        for (int i = 0; i < n; i++) a[i] = x[i] + d[i], b[i] = x[i] - d[i];
        vector<int64_t> dx = x;
        for (auto& v : dx) v *= 2;

        // abs(x[i] - x[p]) + abs(x[j] - x[q]) + d[i] + d[j] + c <= target
        // x[i] - x[p] + x[j] - x[q] + d[i] + d[j] + c <= target
        // x[p] - x[i] + x[j] - x[q] + d[i] + d[j] + c <= target
        // x[i] - x[p] + x[q] - x[j] + d[i] + d[j] + c <= target
        // x[p] - x[i] + x[q] - x[j] + d[i] + d[j] + c <= target

        // x[p] + x[q] >= x[i] + x[j] + d[i] + d[j] + c - target
        // x[p] + x[q] <= x[i] + x[j] - d[i] - d[j] - c + target
        // x[q] - x[p] <= x[j] - x[i] - d[i] - d[j] - c + target
        // x[q] - q[p] >= x[j] - x[i] + d[i] + d[j] + c - target

        // k := c - target
        // x[p] + x[q] >= (x[i] + d[i]) + (x[j] + d[j]) + k
        // x[p] + x[q] <= (x[i] - d[i]) + (x[j] - d[j]) - k
        // x[q] - x[p] <= (x[j] - d[j]) - (x[i] + d[i]) - k
        // x[q] - x[p] >= (x[j] + d[j]) - (x[i] - d[i]) + k

        // x[p] + x[q] >= a[i] + a[j] + k
        // x[p] + x[q] <= b[i] + b[j] - k
        // x[q] - x[p] <= b[j] - a[i] - k
        // x[q] - x[p] >= a[j] - b[i] + k

        // x[p] + x[q] + x[q] - x[p] >= a[i] + a[j] + a[j] - b[i] + k + k

        // x[p] + x[q] + x[q] - x[p] <= b[i] + b[j] + b[j] - a[i] - k - k

        // x[p] + x[q] - x[q] + x[p] >= a[i] + a[j] + k - b[j] + a[i] + k

        // x[p] + x[q] - x[q] + x[p] <= b[i] + b[j] - k - a[j] + b[i] - k

        // x[q] * 2 >= a[i] - b[i] + a[j] * 2 + k * 2
        // x[q] * 2 <= b[i] - a[i] + b[j] * 2 - k * 2
        // x[p] * 2 >= a[j] - b[j] + a[i] * 2 + k * 2
        // x[p] * 2 <= b[j] - a[j] + b[i] * 2 - k * 2

        auto check = [&](int64_t target) {
                int64_t low_p = -1e18, high_p = +1e18;
                int64_t low_q = -1e18, high_q = +1e18;
                int64_t k = c - target;
                for (int i = 0; i < n; i++) {
                        for (int j = i + 1; j < n; j++) {
                                if (x[j] - x[i] + d[i] + d[j] > target) {
                                        low_p = max(low_p, a[j] - b[j] + a[i] * 2 + k * 2);
                                        high_p = min(high_p, b[j] - a[j] + b[i] * 2 - k * 2);
                                        low_q = max(low_q, a[i] - b[i] + a[j] * 2 + k * 2);
                                        high_q = min(high_q, b[i] - a[i] + b[j] * 2 - k * 2);
                                }
                        }
                }
                if (low_p > high_p || low_q > high_q) return 0;
                int64_t p = lower_bound(dx.begin(), dx.end(), low_p) - dx.begin();
                int64_t q = upper_bound(dx.begin(), dx.end(), high_q) - dx.begin() - 1;
                if (p == n || dx[p] > high_p) return 0;
                if (q < 0 || dx[q] < low_q) return 0;
                if (p >= q) return 0;
                return 1;
        };

        int64_t low = 0, high = 1ll << 60;
        while (low < high) {
                int64_t mid = low + high >> 1;
                if (check(mid)) {
                        high = mid;
                } else {
                        low = mid + 1;
                }
        }
        return high;
}

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

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:74:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |                 int64_t mid = low + high >> 1;
      |                               ~~~~^~~~~~

• 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