QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241793 | #7651. 傅里叶与交通规划 | hos_lyric# | 15 | 52ms | 8956kb | C++14 | 3.4kb | 2023-11-06 17:27:42 | 2024-07-04 02:22:57 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
using Double = double;
constexpr Double INF = 1e+100;
int N, Q;
Int V;
vector<Int> P;
vector<Int> W;
vector<Int> X0, Y0, X1, Y1;
int indexOf(Int x) {
return (upper_bound(P.begin(), P.end(), x) - P.begin()) - 1;
}
namespace brute {
vector<Int> fs;
Int calc(Int x) {
const int i = indexOf(x);
if (i < 0) return 0;
if (i >= N) return fs[N];
return fs[i] + W[i] * (x - P[i]);
}
vector<Double> run() {
cerr<<"[brute::run]"<<endl;
fs.assign(N + 1, 0);
for (int i = 0; i < N; ++i) {
fs[i + 1] = fs[i] + W[i] * (P[i + 1] - P[i]);
}
vector<Double> ans(Q, INF);
for (int q = 0; q < Q; ++q) {
const Int f0 = calc(X0[q]);
const Int f1 = calc(X1[q]);
auto check = [&](int i, Int x, Int f) -> void {
const Int w = (0 <= i && i < N) ? W[i] : 0;
Int dx = 0, dy = 0;
dx += abs(x - X0[q]);
dx += abs(x - X1[q]);
dy += (X0[q] <= x) ? (f - f0) : (f0 - f);
dy += (X1[q] <= x) ? (f - f1) : (f1 - f);
/*
yoko: (dx/V) sec
tate: katteni (dy/V)
*/
Double cost = 0.0;
cost += (Double)dx / V;
if (V * (Y1[q] - Y0[q]) >= dy) {
cost += ((Y1[q] - Y0[q]) - (Double)dy / V) / (w + V);
} else {
cost += ((Y1[q] - Y0[q]) - (Double)dy / V) / (w - V);
}
// cerr<<"check i="<<i<<" x="<<x<<" f="<<f<<": w="<<w<<", dx="<<dx<<", dy="<<dy<<", cost="<<cost<<endl;
chmin(ans[q], cost);
};
const int i0 = indexOf(X0[q]);
check(i0, X0[q], f0);
for (int i = 0; i <= N; ++i) {
check(i - 1, P[i], fs[i]);
check(i , P[i], fs[i]);
}
}
return ans;
}
} // brute
int main() {
for (; ~scanf("%d%d%lld", &N, &Q, &V); ) {
P.resize(N + 1);
for (int i = 0; i <= N; ++i) {
scanf("%lld", &P[i]);
}
W.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%lld", &W[i]);
}
X0.resize(Q);
Y0.resize(Q);
X1.resize(Q);
Y1.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%lld%lld%lld%lld", &X0[q], &Y0[q], &X1[q], &Y1[q]);
}
const auto ans = brute::run();
for (int q = 0; q < Q; ++q) {
printf("%.8f\n", ans[q]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 52ms
memory: 8956kb
input:
0 149997 245221 260130 -353413 28107 189392 258734 122083 -105519 88981 -462313 62982 -221175 258110 442570 177977 -216904 -444299 246103 134500 179401 -402939 -459279 98037 -470438 -69318 43668 -204852 443991 -303144 -468157 -19237 -321861 40988 -450597 298668 -155343 -121990 491091 -446262 2335 -...
output:
3.15402025 1.58997802 3.50244473 4.42573434 4.79615938 2.77896673 4.12052801 0.77057430 4.35155227 0.78707370 2.41183259 3.24564780 4.03301512 2.32130609 1.24432655 4.13647281 2.06239270 2.43803345 2.29035441 2.68600976 3.05624314 3.45513639 3.94013155 2.41386749 4.75957198 3.09785867 0.37262714 0.3...
result:
ok 149997 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
0 100 180744 464809 345260 -467272 -358539 328967 -47960 301643 54141 -6592 -43596 319458 -354462 -459419 -92196 310800 -85882 335949 153982 440647 336749 -116156 101998 -66169 149181 43052 -149130 -353 -398781 416947 -291725 221463 -136712 391161 105694 -5114 87525 234469 21942 -235999 209836 6442...
output:
8.29924092 2.27026070 6.02920706 0.17407493 4.09180941 0.86533440 3.69003120 1.79652437 1.42606117 2.70171071 2.86964436 4.16984243 3.87484508 4.18178750 4.62944828 3.62348404 3.76117050 2.17181207 3.82678263 1.22877661 4.10372129 2.52296065 2.96553689 4.42727283 3.63646373 2.52484177 5.38372505 6.7...
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
0 96 112916 108050 -365188 332547 492134 -36526 -104666 473952 170125 173190 -234758 166079 187562 394112 -60172 -420595 -214538 460150 10825 55480 -120065 416458 351912 -140831 -73406 308683 -217445 -459449 51277 -72378 -176912 150232 144434 162328 -50628 -400429 -319790 -371228 327358 480500 3347...
output:
10.86112686 5.09717843 5.75961777 9.16708881 4.35605229 7.74763541 5.80779518 2.95300932 2.64234475 3.16722165 4.35376740 4.60013638 8.28630132 2.48132240 9.70007793 5.11102058 1.89044954 11.16963938 11.24308335 9.67789330 11.31193985 5.80470438 6.70501080 2.60430763 2.29521946 6.76313366 3.44829785...
result:
ok 96 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
0 98 22895 91189 -107939 77752 -276636 60647 386902 -56253 293764 -430313 231497 65839 344043 304956 -391967 441156 -160698 -32346 -64780 -107106 -221509 484371 -91709 224130 432009 480623 -489838 249592 -392494 -46576 -467214 -156595 -15098 -382701 -34447 443533 154513 317948 8797 -276399 434059 7...
output:
8.11539637 20.40611487 15.35981655 30.78274732 32.67988644 34.07778991 17.18768290 29.62314916 13.73858921 33.91945840 21.46490500 45.53858921 63.71260100 37.09071850 44.31640096 31.28464730 36.31661935 30.56217515 14.79423455 34.37287617 43.04564315 9.60397467 19.62590085 41.22747325 36.55562350 28...
result:
ok 98 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
0 100 150548 10776 -338992 -479131 59003 172812 -231402 248648 269139 168600 -447255 262673 -479943 129977 266443 -494085 -99721 -439611 -328970 -239053 151827 -95253 144393 282865 221465 477090 265238 -268953 117580 107627 -320233 -224623 -394376 -382842 260411 288143 362003 -231710 -327178 195775...
output:
6.97410793 3.85650424 1.09854664 2.79404575 4.14882297 1.80206313 3.48219837 1.54344129 4.12788612 1.54292983 5.65552515 2.31542100 7.00387916 2.47851184 4.89175545 6.34711853 8.74582193 3.32192390 1.27725377 2.92590403 4.03245477 5.15509339 7.35045965 6.13361187 6.32190398 5.31443128 4.88996201 4.3...
result:
ok 100 numbers
Subtask #2:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 14ms
memory: 3996kb
input:
993 999 316326 -496532 -496093 -495620 -492330 -492168 -490309 -490221 -489706 -489674 -488540 -487445 -487205 -487063 -486731 -486636 -486525 -483675 -483348 -482170 -480225 -478996 -477851 -477476 -476245 -474426 -473611 -473054 -472532 -470524 -470223 -469519 -469003 -468790 -468648 -468210 -4680...
output:
0.99010577 1.57607674 2.57334584 2.67164505 2.52050013 2.59312045 1.12071575 3.34263720 0.35232732 3.94401275 2.03752604 1.98331717 2.35556910 1.09670729 3.20188003 0.71721534 2.19390824 1.56526473 2.40689070 1.58574632 0.91850959 2.55687581 0.83284001 0.76295398 1.37607412 2.91979169 1.08532667 3.4...
result:
ok 999 numbers
Test #7:
score: 0
Accepted
time: 14ms
memory: 4136kb
input:
997 997 217603 -499799 -498333 -497404 -496957 -496655 -494826 -493913 -493091 -492990 -491277 -490056 -488767 -486657 -486543 -486528 -484217 -480512 -479591 -479562 -479559 -479159 -475469 -475297 -474181 -472973 -472661 -471212 -469422 -468661 -467326 -466468 -466262 -466067 -465341 -464845 -4643...
output:
1.10315413 2.04213627 2.80220658 2.96301554 1.25719017 0.59102322 2.00148114 1.38669390 0.49166153 2.50589746 2.63206611 1.11855330 1.72002029 3.93561193 1.87906938 2.36731687 5.85708015 0.15208288 1.18437640 5.54827737 2.12456558 3.09177448 3.97089190 1.95963096 2.62222884 3.66790539 3.31215838 1.7...
result:
ok 997 numbers
Test #8:
score: 0
Accepted
time: 14ms
memory: 4092kb
input:
990 999 410563 -499636 -499493 -498362 -497772 -496607 -496251 -495502 -495291 -493565 -492200 -491876 -491569 -490203 -488666 -488637 -486272 -484197 -483586 -482754 -478432 -477269 -475235 -475067 -474547 -473480 -473411 -472262 -472236 -471888 -471339 -470160 -469159 -468072 -467881 -467211 -4661...
output:
1.45568369 0.85106182 1.59002304 1.63750780 1.47689464 0.87829694 0.52454148 0.70728837 1.00942848 1.21703711 0.55728022 0.96556329 0.76301772 1.66156757 1.47066171 1.42251255 2.14472562 0.86770401 2.48698503 0.58205739 1.12521280 0.84184861 0.99341925 0.89837199 0.79614209 1.49971601 1.10132344 0.5...
result:
ok 999 numbers
Test #9:
score: 0
Accepted
time: 14ms
memory: 3836kb
input:
999 991 278604 -499261 -498572 -498286 -495372 -493428 -492225 -490363 -487496 -487171 -485925 -484689 -484522 -483834 -482217 -481524 -481508 -479914 -478464 -477272 -476511 -475715 -475488 -475103 -473881 -472520 -471545 -468813 -467921 -467847 -467545 -465121 -464313 -462531 -462228 -461384 -4602...
output:
3.02300376 2.35961578 3.53346494 2.09374885 2.54324049 2.98178258 2.65666740 0.90686289 1.38028495 2.28961727 1.84235312 2.71083706 2.04573392 3.46622063 3.35640086 3.86226570 5.07207131 1.67539852 2.26548459 0.43374126 1.33803913 0.41368930 1.71830339 2.56779661 3.55257242 2.85706133 2.03814615 3.3...
result:
ok 991 numbers
Test #10:
score: 0
Accepted
time: 14ms
memory: 3960kb
input:
998 995 86259 -499764 -499107 -497424 -497246 -496766 -496696 -495855 -495537 -494905 -494468 -490023 -488774 -487401 -486388 -484946 -483405 -483153 -482740 -481457 -480043 -479973 -477456 -477212 -477029 -476323 -473012 -472991 -472761 -472734 -472112 -471906 -471690 -471578 -469858 -469637 -46872...
output:
5.51117669 5.94012013 12.87262087 4.94578325 2.31966038 10.89187986 12.02043319 7.68111978 3.24887869 10.40333746 12.58159340 9.71068730 2.15219750 6.12110270 10.75168657 7.34640668 8.21922217 8.60182083 8.64925664 12.41368190 4.77069304 8.28747830 2.55960575 9.92515972 9.05260941 13.00865596 7.4206...
result:
ok 995 numbers
Subtask #3:
score: 0
Time Limit Exceeded
Test #11:
score: 0
Time Limit Exceeded
input:
149928 149904 81074 -499992 -499987 -499981 -499968 -499965 -499961 -499949 -499941 -499940 -499933 -499925 -499923 -499911 -499899 -499893 -499892 -499877 -499868 -499865 -499858 -499852 -499849 -499845 -499838 -499837 -499836 -499826 -499822 -499819 -499815 -499803 -499801 -499797 -499785 -499783 ...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Time Limit Exceeded
Test #27:
score: 0
Time Limit Exceeded
input:
149957 149927 72015 -499992 -499989 -499986 -499981 -499980 -499970 -499957 -499950 -499947 -499937 -499929 -499928 -499925 -499915 -499913 -499905 -499885 -499881 -499868 -499859 -499856 -499852 -499848 -499839 -499835 -499828 -499821 -499815 -499814 -499809 -499808 -499799 -499797 -499792 -499783 ...
output:
result:
Subtask #6:
score: 0
Time Limit Exceeded
Test #34:
score: 0
Time Limit Exceeded
input:
149278 149093 342851 -499997 -499996 -499993 -499975 -499974 -499969 -499955 -499954 -499942 -499939 -499935 -499934 -499926 -499905 -499901 -499895 -499893 -499883 -499882 -499872 -499865 -499862 -499859 -499815 -499807 -499805 -499799 -499779 -499765 -499755 -499741 -499736 -499729 -499701 -499688...
output:
result:
Subtask #7:
score: 0
Time Limit Exceeded
Test #43:
score: 0
Time Limit Exceeded
input:
149990 149944 141363 -499995 -499994 -499993 -499990 -499956 -499950 -499947 -499924 -499921 -499916 -499914 -499888 -499876 -499870 -499869 -499863 -499855 -499848 -499846 -499837 -499836 -499833 -499832 -499815 -499813 -499799 -499787 -499775 -499770 -499769 -499767 -499766 -499762 -499757 -499753...
output:
result:
Subtask #8:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Test #48:
score: 0
Time Limit Exceeded
input:
49982 49912 98988 -499997 -499929 -499912 -499874 -499844 -499825 -499814 -499742 -499709 -499646 -499643 -499626 -499602 -499579 -499554 -499512 -499509 -499507 -499483 -499479 -499381 -499365 -499223 -499204 -499192 -499179 -499147 -499144 -499120 -499046 -499020 -498997 -498994 -498955 -498954 -4...
output:
result:
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #4:
0%