| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 502689 |
2022-01-06T12:52:43 Z |
blue |
Shortcut (IOI16_shortcut) |
C++17 |
|
0 ms |
0 KB |
#include "shortcut.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
const int mxn = 1'000'000;
const ll INF = 1'000'000'000'000'000'000LL;
vll x(1+mxn);
vll y(1+mxn);
vll xpy(1+mxn);
vll xdy(1+mxn);
vll ydx(1+mxn);
long long find_shortcut(int n, vector<int> l_, vector<int> d_, int c_)
{
x[1] = 0;
for(int i = 2; i <= n; i++) x[i] = x[i-1] + l_[i-2];
for(int i = 1; i <= n; i++) y[i] = d_[i-1];
ll l = c_; //shortcut length
for(int i = 1; i <= n; i++)
{
xpy[i] = x[i] + y[i];
xdy[i] = x[i] - y[i];
ydx[i] = -xdy[i];
}
int* ord = new int[1+n];
for(int i = 1; i <= n; i++) ord[i] = i;
sort(ord+1, ord+n+1, [] (int u, int v)
{
return ydx[u] > ydx[v];
});
// cerr << "\n\n\n";
// for(int i = 1; i <= n; i++) cerr << i << " : " << x[i] << ' ' << y[i] << ' ' << y[i] - x[i] << '\n';
//
// cerr << "ord = ";
// for(int oi = 1; oi <= n; oi++) cerr << ord[oi] << ' ';
// cerr << '\n';
// cerr << "\n\n\n";
pair<ll, int> xpy_max[1+n], xpy_max2[1+n];
xpy_max[0] = xpy_max2[0] = {-INF, 0};
// xpy_max[1] = {x[ord[1]] + y[ord[1]], ord[1]};
// xpy_max2[1] = {-INF, 0};
// cerr << "COMPUTING MAX\n";
for(int i = 1; i <= n; i++)
{
xpy_max[i] = xpy_max[i-1];
xpy_max2[i] = xpy_max2[i-1];
pair<ll, int> nw = {xpy[ord[i]], ord[i]};
if(nw <= xpy_max2[i]) ;
else if(nw <= xpy_max[i]) xpy_max2[i] = nw;
else
{
xpy_max2[i] = xpy_max[i];
xpy_max[i] = nw;
}
// cerr << "element = " << ord[i] << " : ";
// cerr << xpy_max[i].first << "|" << xpy_max[i].second << " , " << xpy_max2[i].first << "|" << xpy_max2[i].second << '\n';
}
// cerr << "\n\n\n\n";
// cerr << "COMPUTING MIN\n";
pair<ll, int> xdy_min[1+3], xdy_min2[1+3];
xdy_min[0] = xdy_min2[0] = {INF, 0};
for(int i = 1; i <= 2; i++)
{
xdy_min[i] = xdy_min[i-1];
xdy_min2[i] = xdy_min2[i-1];
pair<ll, int> nw = {xdy[ord[i]], ord[i]};
if(nw >= xdy_min2[i]);
else if(nw >= xdy_min[i]) xdy_min2[i] = nw;
else
{
xdy_min2[i] = xdy_min[i];
xdy_min[i] = nw;
}
// cerr << "element = " << ord[i] << " : ";
// cerr << xdy_min[i].first << "|" << xdy_min[i].second << " , " << xdy_min2[i].first << "|" << xdy_min2[i].second << '\n';
}
// sort(ord+1, ord+n+1, [] (int u, int v)
// {
// return y[u] - x[u] > y[v] - x[v];
// });
vi I(n);
for(int i = 0; i < n; i++) I[i] = i+1;
sort(I.begin(), I.end(), [] (int u, int v)
{
return xpy[u] < xpy[v];
});
ll lo = 1;
// ll hi = (1'000'000'000'000'000'000LL);
ll hi = 2'000'000'000LL + x[n] - x[1];
while(lo != hi)
{
ll k = (lo+hi)/2;
// cerr << "\n\n\n";
// cerr << "k = " << k << '\n';
ll sum_lo = -INF;
ll sum_hi = INF;
ll diff_lo = -INF;
ll diff_hi = INF;
int i_ind = 0;
for(int q = 0; q < n; q++)
{
int j = I[q];
while(i_ind + 1 <= n && ydx[ord[i_ind+1]] > k - xpy[j])
{
int i = ord[i_ind+1];
if(!(-xdy[i] > k - xpy[j])) break;
i_ind++;
}
// ll xpy_maxval = (xpy_max[i_ind].second != j ? xpy_max[i_ind].first : xpy_max2[i_ind].first);
ll xpy_maxval = xpy_max[i_ind].first;
int d_ind = min(i_ind, 2);
// ll xdy_minval = (xdy_min[d_ind].second != j ? xdy_min[d_ind].first : xdy_min2[d_ind].first);
ll xdy_minval = xdy_min[d_idn].first;
sum_lo = max(sum_lo, xpy_maxval + xpy[j]);
diff_hi = min(diff_hi, xdy[j] - xpy_maxval);
sum_hi = min(sum_hi, xdy_minval + xdy[j]);
diff_lo = max(diff_lo, xpy[j] - xdy_minval);
}
sum_lo += l-k;
diff_hi += k-l;
sum_hi += k-l;
diff_lo += l-k;
// cerr << sum_lo << ' ' << sum_hi << ' ' << diff_lo << ' ' << diff_hi << '\n';
bool works = 0;
// for(int i = 1; i <= n; i++)
// {
// for(int j = i+1; j <= n; j++)
// {
// if(sum_lo <= x[i] + x[j] && x[i] + x[j] <= sum_hi)
// {
// if(diff_lo <= x[j] - x[i] && x[j] - x[i] <= diff_hi)
// {
// works = 1;
// }
// }
// // cerr << "val = " << x[i] + x[j] << ' ' << x[j] - x[i] << '\n';
// }
// }
// // cerr << "works = " << works << '\n';
int b = 1;
for(int a = 1; a <= n; a++)
{
ll ctr = max(sum_lo - x[a], diff_lo + x[a]);
while(b > 1 && x[b-1] >= ctr) b--;
while(b <= n && x[b] < ctr) b++;
if(1 <= b && b <= n)
if(sum_lo <= x[a] + x[b])
if(x[a] + x[b] <= sum_hi)
if(diff_lo <= x[b] - x[a])
if(x[b] - x[a] <= diff_hi)
works = 1;
}
// cerr << lo << ' ' << hi << " -> ";
if(works) hi = k;
else lo = k+1;
// cerr << lo << ' ' << hi << '\n';
}
return lo;
}
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:170:37: error: 'd_idn' was not declared in this scope; did you mean 'd_ind'?
170 | ll xdy_minval = xdy_min[d_idn].first;
| ^~~~~
| d_ind
shortcut.cpp:168:17: warning: unused variable 'd_ind' [-Wunused-variable]
168 | int d_ind = min(i_ind, 2);
| ^~~~~
