Submission #108423

#	Time	Username	Problem	Language	Result	Execution time	Memory
108423		tictaccat	Shortcut (IOI16_shortcut)	C++14	71 / 100	2054 ms	2688 KiB

shortcut

#include "shortcut.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll INF = 1e18;

int n; ll c;
vector<ll> l,d,x;

bool check (ll k) {
    ll delta = k-c;
    ll difMax = INF, difMin = -INF, sumMax = INF, sumMin = -INF;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (x[j] - x[i] + d[i] + d[j] <= k) continue;
            ll delta = k - c - d[i] - d[j];
            difMax = min(x[j]-x[i]+delta, difMax);
            difMin = max(x[j]-x[i]-delta, difMin);
            sumMax = min(x[j]+x[i]+delta, sumMax);
            sumMin = max(x[j]+x[i]-delta, sumMin);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (x[j] - x[i] < difMin) continue;
            if (x[j] - x[i] > difMax) continue;
            if (x[j] + x[i] < sumMin) continue;
            if (x[j] + x[i] > sumMax) continue;
            return true;
        }
    }
    return false;
}

long long find_shortcut(int nt, std::vector<int> lt, std::vector<int> dt, int ct) {

    n = nt; c = ct;
    l.insert(l.end(),lt.begin(), lt.end()); 
    d.insert(d.end(), dt.begin(), dt.end()); 
    x.resize(n);

    for (int i = 1; i < n; i++) x[i] = x[i-1] + l[i-1]; //length sum from left to index i

    ll k = 0;
    ll high = INF;

    for (ll b = high/2; b > 0; b /= 2) {
        while (k + b < high && !check(k+b)) {
            k += b;
          //  cout << k << "\n";
        }
    } 

    return k+1;
}

Compilation message (stderr)

shortcut.cpp: In function 'bool check(ll)':
shortcut.cpp:13:8: warning: unused variable 'delta' [-Wunused-variable]
     ll delta = k-c;
        ^~~~~

• 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