제출 #1287637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287637		vincentbucourt1	Shortcut (IOI16_shortcut)	C++20	71 / 100	2096 ms	1344 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long // careful of int !!!

const ll OO = (ll)1e18;

struct Rect { // x = r - l, y = r + l
    ll xLo, xHi, yLo, yHi;
    bool contains (ll x, ll y) {
        return (xLo <= x && x <= xHi && yLo <= y && y <= yHi);
    }
    void dbg () {
        cerr << "rect: " << xLo << " " << xHi << " " << yLo << " " << yHi << "\n";
    }
};
Rect merge (const Rect& a, const Rect& b) {
    return Rect{max(a.xLo, b.xLo), min(a.xHi, b.xHi), max(a.yLo, b.yLo), min(a.yHi, b.yHi)};
}

bool test (ll UB, int& N, vector<ll>& dist, vector<int>& lenDown, const int& costBridge) {
    // cerr << "test: " << UB << "\n";
    Rect intersection = Rect{-OO, OO, -OO, OO};
    for (int iL = 0; iL < N-1; iL++) {
        for (int iR = iL+1; iR < N; iR++) {
            ll l = dist[iL], r = dist[iR];
            if (r - l + lenDown[iR] + lenDown[iL] > UB) {
                ll delta = UB - costBridge - lenDown[iL] - lenDown[iR];
                if (delta < 0) {
                    return false;
                }
                else {
                    ll xMid = r - l, yMid = r + l;
                    intersection = merge(intersection, Rect{xMid - delta, xMid + delta, yMid - delta, yMid + delta});
                }
            }
        }
    }
    // intersection.dbg();
    bool res = false;
    for (int iL = 0; iL < N-1; iL++) {
        for (int iR = iL+1; iR < N; iR++) {
            ll l = dist[iL], r = dist[iR];
            ll x = r - l, y = r + l;
            if (intersection.contains(x, y)) {
                res = true;
            }
        }
    }
    return res;
}

ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
    vector<ll> dist(N, 0);
    for (int i = 0; i < N-1; i++) {
        dist[i+1] = dist[i] + lenSide[i];
    }
    ll loBS = 0, hiBS = OO;
    while (loBS < hiBS-1) {
        ll midBS = loBS + (hiBS - loBS) / 2;
        assert(loBS <= midBS && midBS <= hiBS);
        if (test(midBS, N, dist, lenDown, costBridge)) {
            hiBS = midBS;
        }
        else {
            loBS = midBS;
        }
    }
    return hiBS;
}

컴파일 시 표준 에러 (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