Submission #805945

#TimeUsernameProblemLanguageResultExecution timeMemory
805945restingShortcut (IOI16_shortcut)C++17
100 / 100
1449 ms81208 KiB
//#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define ll long long const ll inf = 1e18; ll find_shortcut(int n, vector<int> l, vector<int> d, int c) { vector<ll> p(n, 0); for (int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1]; vector<ll> distl(n, 0), distr(n, 0); ll cur = 0; for (int i = 0; i < n; i++) { distl[i] = cur + d[i]; if (i) distl[i] = max(distl[i], distl[i - 1]); cur = max(cur, (ll)d[i]); if (i + 1 < n) cur += l[i]; } cur = 0; for (int i = n - 1; i >= 0; i--) { distr[i] = cur + d[i]; if (i != n - 1) distr[i] = max(distr[i], distr[i + 1]); cur = max(cur, (ll)d[i]); if (i) cur += l[i - 1]; } ll mxmn = 0; for (int i = 0; i < n; i++) { mxmn = max(mxmn, min(distl[i], distr[i])); } vector<pair<ll, int>> partl, partr; //partition left, right ll mud = 0; for (int i = 0; i < n; i++) { if (distl[i] == mxmn) { partl.push_back({ d[i], i }); mud = p[i]; break; } if (distr[i] == mxmn) { partr.push_back({ d[i], i }); mud = p[i]; break; } } for (int i = 0; i < n; i++) { if (p[i] < mud) partl.push_back({ mud - p[i] + d[i], i }); if (p[i] > mud) partr.push_back({ p[i] - mud + d[i], i }); } sort(partl.begin(), partl.end()); sort(partr.begin(), partr.end()); ll left = mxmn - 1, right = inf; while (right - left > 1) { ll mid = (left + right) / 2; ll x1 = -inf, x2 = inf, y1 = -inf, y2 = inf; ll rangl = -inf, rangr = inf; int cur = partr.size() - 1; for (int i = 0; i < partl.size(); i++) { while (cur >= 0 && partr[cur].first + partl[i].first > mid) { rangl = max(rangl, (ll)p[partr[cur].second] - (mid - c - d[partr[cur].second])); rangr = min(rangr, (ll)p[partr[cur].second] + (mid - c - d[partr[cur].second])); //cout << "bruh" << (mid - c - d[partr[cur].second]) << endl; cur--; } // {p[i], rangl}, {p[i], rangr} //rangr > rangl //(x, y) -> (x + y, x - y) rangl += d[partl[i].second]; rangr -= d[partl[i].second]; x1 = max(x1, p[partl[i].second] + rangl); x2 = min(x2, p[partl[i].second] + rangr); y1 = max(y1, p[partl[i].second] - rangr); y2 = min(y2, p[partl[i].second] - rangl); rangl -= d[partl[i].second]; rangr += d[partl[i].second]; } for (int i = 0; i < n; i++) { ll l2 = -inf, r2 = inf; // x + y > x1, y > x1 - x l2 = max(l2, x1 - p[i]); //x + y < x2, y < x2 - x r2 = min(r2, x2 - p[i]); //x - y > y1, y < x - y1 r2 = min(r2, p[i] - y1); //x - y < y2, y > x - y2 l2 = max(l2, p[i] - y2); if (l2 > r2 || l2 > p.back()) continue; ll x = *lower_bound(p.begin(), p.end(), l2); if (x <= r2) goto pass; } left = mid; continue; pass:; right = mid; } return right; } // ll find_shortcut_correct(int n, vector<int> l, vector<int> d, int c) { // ll res = inf; // vector<ll> p(n, 0); // for (int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1]; // for (int i = 0; i < n; i++) { // for (int j = 0; j < n; j++) { // ll cur = 0; // for (int a = 0; a < n; a++) { // for (int b = 0; b < n; b++) { // cur = max(cur, d[a] + d[b] + min(abs(p[a] - p[b]), abs(p[a] - p[i]) + c + abs(p[a] - p[j]))); // } // } // res = min(res, cur); // } // } // return res; // } // int main() { // cout << find_shortcut(4, { 10, 20, 20 }, { 0, 40, 0, 30 }, 10) << endl; // }

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0; i < partl.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...