Submission #547040

#	Time	Username	Problem	Language	Result	Execution time	Memory
547040		fvogel499	Shortcut (IOI16_shortcut)	C++17	0 / 100	0 ms	304 KiB

shortcut

/*
 * File created on 04/09/2022 at 10:34:35.
 * Link to problem: 
 * Description: 
 * Time complexity: O()
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2022 Francois Vogel
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define int ll
#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int inf = 1e18;

int find_shortcut_act(int n, vi dist, vi at, int extraPath) {
    int prefD [n];
    prefD[0] = 0;
    for (int i = 1; i < n; i++) prefD[i] = prefD[i-1]+dist[i-1];
    int lft [n];
    lft[0] = at[0];
    for (int i = 1; i < n; i++) lft[i] = max(lft[i-1]+dist[i-1], at[i]);
    int rgt [n];
    rgt[n-1] = at[n-1];
    for (int i = n-2; i >= 0; i--) rgt[i] = max(rgt[i+1]+dist[i], at[i]);
    int res = inf;
    for (int _ = (1LL<<60); _; _ /= 2) {
        int prop = res-_;
        if (prop < 0) continue;
        bool poss = false;
        for (int i = 0; i < n; i++) {
            if (lft[i] > prop) break;
            int till = n;
            while (till-1 > i && rgt[till-1]+lft[i]+min(extraPath, prefD[till-1]-prefD[i]) <= prop) till--;
            if (till == n) break;
            if (till <= i+1) {
                poss = true;
                break;
            }
            int len = till-i-1;
            assert(len >= 1);
            int toNext [len];
            for (int j = i+1; j < till-1; j++) toNext[j-i-1] = dist[j-1];
            toNext[len-1] = dist[i]+dist[till-1]+extraPath;
            int prefNext [len];
            prefNext[0] = toNext[0];
            for (int i = 1; i < len; i++) prefNext[i] = prefNext[i-1]+toNext[i];
            int locAt [len];
            for (int j = 0; j < len; j++) locAt[j] = at[i+j+1];
            bool ok = true;
            int k = 0;
            int mx = 0, sum = 0;
            for (int j = 0; j < len; j++) {
                if (j) {
                    mx -= toNext[j-1];
                    sum -= toNext[j-1];
                }
                while (sum+toNext[k] <= prefNext[len-1]/2LL) {
                    sum += toNext[k];
                    k++;
                    k %= len;
                    mx = max(mx, sum+locAt[k]);
                }
                if (mx+at[j] > prop) {
                    ok = false;
                    break;
                }
                if (at[j]+prefD[j]-prefD[i]+lft[i] > prop || at[j]+prefD[till]-prefD[j]+rgt[till] > prop) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                poss = true;
                break;
            }
        }
        if (poss) {
            res = prop;
        }
    }
    return res;
}

int find_shortcut(signed n, vector<signed> iL, vector<signed> iD, signed c) {
    vi toL, toD;
    for (int i : iL) toL.pb(i);
    for (int i : iD) toD.pb(i);
    return find_shortcut_act(n, toL, toD, c);
}

// signed main() {
//     cin.tie(0);
//     ios_base::sync_with_stdio(0);

//     int n, c;
//     cin >> n >> c;
//     vector<signed> Il(n-1), Id(n);
//     for (int i = 0; i < n-1; i++) cin >> Il[i];
//     for (int i = 0; i < n; i++) cin >> Id[i];
//     cout << find_shortcut(n, Il, Id, c);

//     cout.flush();
//     int d = 0;
//     d++;
// }

• 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