Submission #1287597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287597		vincentbucourt1	Shortcut (IOI16_shortcut)	C++20	0 / 100	2 ms	344 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;}
    bool empty () {
        return !(minX <= maxX && minY <= maxY);
    }
    void dbg () {
        cerr << minX << " " << maxX << ", " << minY << " " << maxY << "\n";
    }
};
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];
                ll minL = lower_bound(distFrom0.begin(), distFrom0.end(), distFrom0[l] - delta) - distFrom0.begin();
                ll maxL = upper_bound(distFrom0.begin(), distFrom0.end(), distFrom0[l] + delta) - distFrom0.begin() - 1;
                ll minR = lower_bound(distFrom0.begin(), distFrom0.end(), distFrom0[r] - delta) - distFrom0.begin();
                ll maxR = upper_bound(distFrom0.begin(), distFrom0.end(), distFrom0[r] + delta) - distFrom0.begin() - 1;
                // cerr << "add rect: " << minL << " " << maxL << ", " << minR << " " << maxR << "\n";
                rotateRect rectOn = rotateRect(minL + minR, maxL + maxR, minL - maxR, maxL - minR);
                finalIntersect = intersection(finalIntersect, rectOn);
            }
        }
    }
    // cerr << "ubDist: " << ubDist << ", dbg ";
    // finalIntersect.dbg();
    // cerr << "\n";
    return !finalIntersect.empty();
}

ll find_shortcut(int N, std::vector<int> lenSide, std::vector<int> lenDown, int 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;
}

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: 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