Submission #1051466

#TimeUsernameProblemLanguageResultExecution timeMemory
1051466Alihan_8Shortcut (IOI16_shortcut)C++17
71 / 100
2066 ms199204 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ar array using i64 = long long; struct square{ i64 x1, x2, y1, y2; square(i64 x1 = 0, i64 x2 = 0, i64 y1 = 0, i64 y2 = 0) : x1(x1), x2(x2), y1(y1), y2(y2) {} square f(square q){ return square(max(x1, q.x1), min(x2, q.x2), max(y1, q.y1), min(y2, q.y2)); } bool check(i64 x, i64 y){ return x1 <= x && x2 >= x && y1 <= y && y2 >= y; } }; long long find_shortcut(int n, std::vector<int> L, std::vector<int> d, int C){ vector <i64> x(n); for ( int i = 1; i < n; i++ ){ x[i] = x[i - 1] + L[i - 1]; } auto ok = [&](i64 k){ i64 kk = k - C; vector <ar<i64,3>> pt; for ( int i = 0; i < n; i++ ){ for ( int j = i + 1; j < n; j++ ){ if ( abs(x[i] - x[j]) + d[i] + d[j] <= k ){ continue; } pt.pb({x[i] + x[j], x[i] - x[j], kk - (d[i] + d[j])}); } } if ( pt.empty() ) return true; auto [X, Y, d] = pt[0]; square t = square( - d, X + d, Y - d, Y + d); for ( int i = 1; i < (int)pt.size(); i++ ){ auto [x, y, d] = pt[i]; t = t.f(square(x - d, x + d, y - d, y + d)); } bool flag = false; for ( int i = 0; i < n; i++ ){ for ( int j = i + 1; j < n; j++ ){ flag |= t.check(x[i] + x[j], x[i] - x[j]); } } return flag; }; i64 l = 0, r = 1e15; while ( l < r ){ i64 m = (l + r) / 2; if ( ok(m) ){ r = m; } else l = m + 1; } return l; }
#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...