제출 #1287618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287618		vincentbucourt1	Shortcut (IOI16_shortcut)	C++20	0 / 100	1 ms	348 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 rotateRect {
    // X = R+L
    // Y = R-L
    ll minX, maxX;
    ll minY, maxY;
    rotateRect (ll a, ll b, ll c, ll d) {minX=a,maxX=b,minY=c,maxY=d;}
    void dbg () {
        cerr << minX << " " << maxX << ", " << minY << " " << maxY << "\n";
    }
    bool inside (int x, int y) {
        return (minX <= x && x <= maxX && minY <= y && y <= maxY);
    }
};
rotateRect intersection (rotateRect& a, rotateRect& b) {
    return rotateRect(max(a.minX, b.minX), min(a.maxX, b.maxX), max(a.minY, b.minY), min(a.maxY, b.maxY));
}

bool test (ll ubDist, const int& N, const vector<int>& lenSide, const vector<int>& lenDown, const int& costBridge) {
    vector<ll> distFrom0(N, 0);
    for (int i = 0; i < N-1; i++) {
        distFrom0[i+1] = distFrom0[i] + lenSide[i];
    }
    rotateRect finalIntersect = rotateRect(-OO, OO, -OO, OO);
    for (int l = 0; l < N-1; l++) {
        for (int r = l+1; r < N; r++) {
            ll distLR = distFrom0[r] - distFrom0[l];
            if (distLR + lenDown[l] + lenDown[r] > ubDist) {
                ll delta = ubDist - costBridge - lenDown[l] - lenDown[r];
                int prefL = distFrom0[l], prefR = distFrom0[r];
                rotateRect rectOn = rotateRect(prefR + prefL - delta, prefR + prefL + delta, prefR - prefL - delta, prefR - prefL + delta);
                finalIntersect = intersection(finalIntersect, rectOn);
            }
        }
    }
    bool ans = false;
    for (int l = 0; l < N-1; l++) {
        for (int r = l+1; r < N; r++) {
            if (finalIntersect.inside(distFrom0[l]+distFrom0[r], distFrom0[r]-distFrom0[l])) {
                // cerr << "works: " << l << ", " << r << "\n";
                ans = true;
            }
        }
    }
    // cerr << "ubDist: " << ubDist << ", dbg ";
    // finalIntersect.dbg();
    // cerr << "ans: " << ans << "\n\n";
    return ans;
}

ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int costBridge) {
    test(110, N, lenSide, lenDown, costBridge);
    ll lBS = 0, rBS = OO;
    while (lBS < rBS-1) {
        ll midBS = lBS + (rBS - lBS) / 2;
        if (test(midBS, N, lenSide, lenDown, costBridge)) {
            rBS = midBS;
        }
        else {
            lBS = midBS;
        }
    }
    return rBS;
}

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