Submission #990508

#	Time	Username	Problem	Language	Result	Execution time	Memory
990508		AdamGS	Shortcut (IOI16_shortcut)	C++17	71 / 100	2067 ms	4024 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e6+7;
ll P[LIM], T[LIM], n, C;
bool check(ll k) {
  ll xpy_dol=-INF, xpy_gora=INF, ymx_dol=0, ymx_gora=INF;
  rep(b, n) rep(a, b) if(T[a]-P[a]>k-P[b]-T[b]) {
    xpy_dol=max(xpy_dol, P[a]+T[a]+P[b]+T[b]-k+C);
    xpy_gora=min(xpy_gora, P[a]-T[a]+P[b]-T[b]+k-C);
    ymx_dol=max(ymx_dol, T[a]-P[a]+P[b]+T[b]-k+C);
    ymx_gora=min(ymx_gora, -P[a]-T[a]+P[b]-T[b]+k-C);
  }
  rep(b, n) rep(a, b) if(xpy_dol<=P[a]+P[b] && P[a]+P[b]<=xpy_gora && ymx_dol<=P[b]-P[a] && P[b]-P[a]<=ymx_gora) return true;
  return false;
}
ll find_shortcut(int _n, vector<int>_l, vector<int>_d, int _c) {
  n=_n; C=_c;
  rep(i, n-1) P[i+1]=P[i]+_l[i];
  rep(i, n) T[i]=_d[i];
  ll po=0, ko=3000000000000000;
  while(po<ko) {
    ll sr=(po+ko)/2;
    if(check(sr)) ko=sr; else po=sr+1;
  }
  return po;
}

• 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