Submission #949571

#	Time	Username	Problem	Language	Result	Execution time	Memory
949571		definitelynotmee	Shortcut (IOI16_shortcut)	C++17	71 / 100	2032 ms	2252 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define O_O
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double dbl;
typedef long double dbll; 
const ll INFL = 2e18+25;
const int INF = 1e9+42;
const double EPS = 1e-7;
const int MOD = (1<<23)*17*7 + 1; // 998244353
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

vector<ll> x;

struct rhombus{
    ll d1mn, d1mx, d2mn, d2mx;

    rhombus(ll a, ll b, ll c, ll d) : d1mn(a), d1mx(b), d2mn(c), d2mx(d){}

    rhombus(ll x, ll y, ll dist){
        ll d1 = x+y, d2 = x-y;

        d1mn = d1-dist, d1mx = d1+dist, d2mn = d2-dist, d2mx = d2+dist;
    }

    bool in(ll x, ll y){
        ll d1 = x+y, d2 = x-y;
        return d1mn <= d1 && d1 <= d1mx && d2mn <= d2 && d2 <= d2mx;
    }

    rhombus operator+(rhombus b){
        return rhombus(max(d1mn, b.d1mn), min(d1mx, b.d1mx), max(d2mn, b.d2mn), min(d2mx, b.d2mx));
    }
};

bool test_poss(int n, vector<int> l, vector<int> d, ll c, ll target){
    
    rhombus resp(-INFL,INFL,-INFL,INFL);
    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)
                resp = resp + rhombus(x[i], x[j], target - (c + d[i] + d[j]));
        }
    }

    // cerr << resp.d1mn << ' ' << resp.d1mx << ' ' << resp.d2mn << ' ' << resp.d2mx << '\n';

    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(resp.in(x[i],x[j]))
                return 1;
        }
    }

    return 0;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
    
    x.resize(n);

    x[0] = 0;

    for(int i = 1; i < n; i++)
        x[i] = x[i-1] + l[i-1];
    
    ll ini = 0, fim = 1e16;

    while(ini != fim){
        ll m = (ini + fim)>>1;

        // cerr << ini << ' ' << fim << ' ' << m << endl;
        if(test_poss(n,l,d,c,m))
            fim = m;
        else ini = m+1;
    }

    return ini;
}

• 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