QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242136 | #7651. 傅里叶与交通规划 | youngsystem | 15 | 60ms | 6004kb | C++20 | 3.2kb | 2023-11-06 23:18:32 | 2023-11-06 23:18:32 |
Judging History
answer
#include<bits/stdc++.h>
#define double long double
using namespace std;
inline int read()
{
int n=0,f=1,ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
n=n*10+ch-'0';
ch=getchar();
}
return n*f;
}
int p[200005],v[200005];
int np[200005],nv[200005],ncnt;
int main()
{
int n,q,V,x1,y1,x2,y2;
n=read();
q=read();
V=read();
for(int i=0;i<=n;i++)p[i]=read();
for(int i=1;i<=n;i++)v[i]=read();
if(n==0)
{
for(int i=1;i<=q;i++)
{
x1=read();
y1=read();
x2=read();
y2=read();
printf("%.9lf\n",(fabs(x2-x1)+fabs(y2-y1))/V);
}
return 0;
}
double wy=0,nans=0;
for(int i=1;i<=n;i++)nans+=1.0*(p[i]-p[i-1])/V,wy+=1.0*(p[i]-p[i-1])/V*v[i];
int maxv=0,minv=0;
for(int i=1;i<=n;i++)maxv=max(maxv,v[i]);
for(int i=1;i<=n;i++)minv=min(minv,v[i]);
for(int i=1;i<=q;i++)
{
x1=read();
y1=read();
x2=read();
y2=read();
if(x1==p[0]&&x2==p[n])
{
double ans=nans;
if(y1+wy<y2)
{
ans+=(y2-y1-wy)/(maxv+V);
}
else
{
ans+=(y1+wy-y2)/(V-minv);
}
printf("%.9Lf\n",ans);
continue;
}
if(x1>x2)swap(x1,x2);
double ans=1000000000;
int pos1=0,pos2=0;
ncnt=0;
if(x1<p[0])
{
np[++ncnt]=x1;
nv[ncnt]=0;
pos1=ncnt;
}
if(x2<p[0])
{
np[++ncnt]=x2;
nv[ncnt]=0;
pos2=ncnt;
}
for(int i=0;i<=n-1;i++)
{
np[++ncnt]=p[i];
nv[ncnt]=v[i];
if(x1>=p[i]&&x1<p[i+1])
{
np[++ncnt]=x1;
nv[ncnt]=v[i+1];
pos1=ncnt;
}
if(x2>=p[i]&&x2<p[i+1])
{
np[++ncnt]=x2;
nv[ncnt]=v[i+1];
pos2=ncnt;
}
}
np[++ncnt]=p[n];
nv[ncnt]=v[n];
if(x1>=p[n])
{
np[++ncnt]=x1;
nv[ncnt]=0;
pos1=ncnt;
}
if(x2>=p[n])
{
np[++ncnt]=x2;
nv[ncnt]=0;
pos2=ncnt;
}
np[++ncnt]=np[ncnt-1];
nv[ncnt]=0;
//for(int i=1;i<=ncnt;i++)printf("%d %d\n",np[i],nv[i]);
//printf("%d %d\n",pos1,pos2);
int maxv=-1000000000,minv=1000000000;
for(int i=pos1+1;i<=pos2;i++)maxv=max(maxv,nv[i]);
for(int i=pos1+1;i<=pos2;i++)minv=min(minv,nv[i]);
double wy=0,nans=0;
for(int i=pos1+1;i<=pos2;i++)nans+=1.0*(np[i]-np[i-1])/V,wy+=1.0*(np[i]-np[i-1])/V*nv[i];
if(y1+wy<y2)
{
ans=min(ans,nans+(y2-y1-wy)/(maxv+V));
}
else
{
ans=min(ans,nans+(y1+wy-y2)/(V-minv));
}
printf("%.9Lf\n",ans);
continue;
int nmaxv=maxv,nminv=minv;
double nwy=wy,nnans=nans;
for(int i=pos1;i>=1;i--)
{
nmaxv=max(nmaxv,nv[i]);
nminv=min(nminv,nv[i]);
if(i!=pos1)
{
nwy=nwy+2.0*(np[i+1]-np[i])/V*nv[i+1];
nnans=nnans+2.0*(np[i+1]-np[i])/V;
}
if(y1+nwy<y2)
{
ans=min(ans,nnans+(y2-y1-nwy)/(nmaxv+V));
}
else
{
ans=min(ans,nnans+(y1+nwy-y2)/(V-nminv));
}
}
nmaxv=maxv;
nminv=minv;
nwy=wy;
nnans=nans;
for(int i=pos2;i<=ncnt-1;i++)
{
nmaxv=max(nmaxv,nv[i+1]);
nminv=min(nminv,nv[i+1]);
if(i!=pos2)
{
nwy=nwy+2.0*(np[i]-np[i-1])/V*nv[i];
nnans=nnans+2.0*(np[i]-np[i-1])/V;
}
if(y1+nwy<y2)
{
ans=min(ans,nnans+(y2-y1-nwy)/(nmaxv+V));
}
else
{
ans=min(ans,nnans+(y1+nwy-y2)/(V-nminv));
}
}
printf("%.9Lf\n",ans);
}
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 35ms
memory: 3752kb
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.154020251 1.589978020 3.502444734 4.425734338 4.796159383 2.778966728 4.120528014 0.770574298 4.351552273 0.787073701 2.411832592 3.245647803 4.033015117 2.321306087 1.244326546 4.136472814 2.062392699 2.438033447 2.290354415 2.686009763 3.056243144 3.455136387 3.940131555 2.413867491 4.759571978 ...
result:
ok 149997 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
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.299240915 2.270260700 6.029207055 0.174074935 4.091809410 0.865334396 3.690031204 1.796524366 1.426061169 2.701710707 2.869644359 4.169842429 3.874845085 4.181787501 4.629448280 3.623484044 3.761170495 2.171812066 3.826782632 1.228776612 4.103721285 2.522960652 2.965536892 4.427272828 3.636463728 ...
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 5772kb
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.861126855 5.097178434 5.759617769 9.167088809 4.356052287 7.747635410 5.807795175 2.953009317 2.642344752 3.167221651 4.353767402 4.600136385 8.286301321 2.481322399 9.700077934 5.111020582 1.890449538 11.169639378 11.243083354 9.677893301 11.311939849 5.804704382 6.705010804 2.604307627 2.295219...
result:
ok 96 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 5772kb
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.115396375 20.406114872 15.359816554 30.782747325 32.679886438 34.077789910 17.187682900 29.623149159 13.738589212 33.919458397 21.464905001 45.538589212 63.712601005 37.090718497 44.316400961 31.284647303 36.316619349 30.562175147 14.794234549 34.372876174 43.045643154 9.603974667 19.625900852 41....
result:
ok 98 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3864kb
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.974107926 3.856504238 1.098546643 2.794045753 4.148822967 1.802063129 3.482198369 1.543441294 4.127886123 1.542929830 5.655525148 2.315420995 7.003879161 2.478511837 4.891755453 6.347118527 8.745821931 3.321923905 1.277253766 2.925904031 4.032454765 5.155093392 7.350459654 6.133611871 6.321903977 ...
result:
ok 100 numbers
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 2ms
memory: 3912kb
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.990105774 1.576076735 2.573345837 2.671645048 2.520500130 2.593120446 1.120715748 3.342637200 0.352327323 3.944012751 2.037526041 1.983317166 2.355569101 1.096707292 3.201880034 0.717215342 2.193908243 1.565264732 2.406890700 1.585746319 0.918509593 2.556875807 0.832840012 0.762953975 1.376074119 ...
result:
wrong answer 140th numbers differ - expected: '0.4186010', found: '0.4207142', error = '0.0021132'
Subtask #3:
score: 10
Accepted
Test #11:
score: 10
Accepted
time: 60ms
memory: 4972kb
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:
16.854842545 14.997179707 15.813778226 16.646357600 13.264177342 14.495166102 13.764569791 14.237523346 12.536875169 15.460444904 13.330981334 14.531256810 13.987157937 16.959710997 14.120091148 12.959439637 15.130910211 14.899977785 12.702650669 14.608114288 14.166963915 14.736089462 16.365950021 1...
result:
ok 149904 numbers
Test #12:
score: 0
Accepted
time: 3ms
memory: 4352kb
input:
49934 90 22588 -499984 -499964 -499955 -499950 -499937 -499923 -499867 -499863 -499860 -499854 -499851 -499795 -499784 -499737 -499731 -499729 -499709 -499703 -499701 -499678 -499676 -499673 -499655 -499590 -499587 -499559 -499536 -499488 -499465 -499453 -499447 -499371 -499351 -499338 -499335 -4993...
output:
51.651728086 45.778284980 58.736378549 48.506740984 54.045671505 48.755639711 64.875883209 45.718937996 44.447814587 46.882302688 45.808522943 50.520989165 60.251232226 61.669282431 47.145678449 45.071190348 47.357399490 50.284569986 52.479203629 44.556031446 44.466386806 56.411700637 55.760197560 6...
result:
ok 90 numbers
Test #13:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
4964 92 138367 -499797 -499471 -499299 -499268 -498616 -498541 -498312 -497850 -497119 -496699 -496505 -496336 -496195 -495977 -495739 -495693 -495376 -495255 -495240 -495084 -495061 -494981 -494958 -494841 -494830 -494713 -494615 -494334 -493926 -493804 -493711 -493618 -493583 -493537 -493414 -4930...
output:
8.519111848 7.699644870 8.831042282 7.411499208 10.005889518 8.664943552 8.494535013 8.846602407 7.546515319 8.640015708 8.636020366 7.877686520 8.892982853 7.532016402 8.305465760 7.345877867 8.359598689 7.443961594 8.577035713 8.867740806 7.591685212 7.836289217 9.040761578 8.880273149 8.371100750...
result:
ok 92 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 6004kb
input:
473 91 280891 -499695 -491193 -490954 -488064 -487152 -486813 -486653 -483884 -483780 -483560 -482582 -478635 -477514 -469765 -468404 -463396 -459567 -459150 -458362 -457468 -456519 -455992 -453760 -447451 -445214 -443060 -439883 -438546 -431873 -422100 -416682 -415799 -408108 -403186 -402593 -40244...
output:
4.997154895 4.102545296 4.676812003 4.695926502 3.936381513 3.560085685 3.564359441 4.797745080 4.303785286 4.816918071 3.718445651 4.309362954 3.728820499 4.607903909 3.987170301 3.955256376 3.616833720 3.846154204 4.488279950 4.907580546 4.400889360 3.952805304 5.191794499 4.475210389 5.144116334 ...
result:
ok 91 numbers
Test #15:
score: 0
Accepted
time: 50ms
memory: 4588kb
input:
99944 149372 113369 -499995 -499983 -499979 -499978 -499964 -499950 -499946 -499929 -499923 -499921 -499914 -499893 -499880 -499863 -499831 -499814 -499805 -499796 -499788 -499787 -499781 -499779 -499748 -499747 -499745 -499734 -499700 -499698 -499695 -499688 -499665 -499660 -499640 -499630 -499624 ...
output:
10.669951602 10.225233713 9.404592305 13.110146464 9.458204071 10.672844822 11.122347991 12.136068734 8.940304478 8.867881401 11.122478258 10.218570103 8.864185391 11.126363920 10.238324790 9.260737403 9.332772404 11.397292906 9.524130673 10.606613903 10.615866914 9.631881063 9.465344503 9.021826241...
result:
ok 149372 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
854 92 154270 -498878 -498558 -498030 -496154 -495734 -495439 -494928 -492469 -489873 -489750 -489153 -488956 -486460 -485436 -485019 -484168 -484159 -483513 -482927 -482269 -480851 -480501 -477526 -476301 -475337 -474926 -474617 -473968 -471575 -471389 -471126 -470407 -469246 -468844 -468789 -46854...
output:
7.005935397 6.621191241 7.107362158 7.126632086 6.560447032 6.694409186 6.771649312 9.309817996 8.035454166 7.375451667 6.740306180 7.164722666 7.178137973 6.708056692 7.898298243 6.492302720 6.491418343 8.446684188 6.608501662 7.020052490 7.324399329 7.153881703 7.086492124 9.428718932 7.029732561 ...
result:
ok 92 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
811 97 204269 -499023 -498121 -496051 -494631 -493384 -492924 -492159 -491576 -489519 -488007 -487026 -485511 -484439 -483918 -480089 -479139 -478859 -475982 -475457 -472489 -472374 -471297 -468837 -468199 -466579 -464763 -463487 -462936 -461462 -459463 -457411 -454221 -453778 -453325 -448427 -44791...
output:
6.369392579 6.323277952 5.325988849 6.972367463 6.490949471 6.885601634 5.019944064 5.143984580 4.939680319 4.891963792 5.520017530 6.894576734 5.252945220 5.221008342 5.007758069 6.293876847 7.155552559 6.900544624 6.440427161 5.610743970 5.296497154 4.922087313 5.117183700 5.248782492 4.899194112 ...
result:
ok 97 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
44 92 23756 -455424 -411003 -394907 -345645 -344017 -301113 -285315 -272511 -248317 -205733 -183557 -179295 -160321 -90555 -61719 -60568 -48097 -47091 -38706 -35645 -31598 -17875 -6000 27003 53825 80267 80971 87486 110173 117577 117796 144115 145782 190489 221315 284071 317664 361721 369142 388959 3...
output:
56.890695667 52.799299581 43.138689545 41.267474939 47.430741584 43.162609956 39.864698072 45.861460442 44.719185882 47.912517029 46.514113181 52.614812912 39.838753617 58.176822266 42.706304279 47.825343738 42.532829700 44.356790548 50.746123676 48.038530834 54.345672773 45.928959693 54.765641926 4...
result:
ok 92 numbers
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #3:
100%
Accepted
Test #19:
score: 0
Time Limit Exceeded
input:
149911 149947 116886 -499997 -499992 -499991 -499971 -499963 -499944 -499929 -499919 -499901 -499896 -499889 -499885 -499874 -499872 -499869 -499865 -499857 -499851 -499846 -499839 -499830 -499829 -499828 -499820 -499817 -499810 -499809 -499789 -499777 -499773 -499771 -499770 -499769 -499764 -499763...
output:
5.035003463 6.800691961 7.420411756 4.777558111 5.918771205 5.488782819 7.209685507 5.549923270 8.268681865 5.110204409 4.925836333 7.661360922 6.112450273 5.510233498 4.985060567 7.313798861 5.975396933 6.031235539 7.365674636 5.628490023 5.989013288 6.448679299 7.737313426 5.453585831 5.778094537 ...
result:
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:
1.435700585 29.029168669 8.075952837 11.508432451 15.186311828 3.439717654 7.035018433 6.225389451 6.452897039 9.495822859 14.321314851 4.135554352 10.888586233 15.763562291 15.415990132 10.887172404 10.123937287 15.254337237 5.923468900 9.191073911 7.063501899 4.937358708 1.777237455 7.759501105 11...
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:
2.824293500 1.782084765 8.666547034 1.241111310 1.105675418 0.487357657 0.192735565 0.155730339 1.018077456 0.295383923 0.189624930 2.653253769 0.031003306 0.402871534 0.347476712 0.876061088 1.118773803 0.513116597 0.615904573 1.043476759 0.037327481 0.106188082 0.640363642 1.090685652 0.910777987 ...
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:
2.859057934 1.316713881 3.128828224 6.234747303 5.073930362 3.695245232 3.291371429 5.500283300 1.289316685 2.420872216 0.739931267 0.918829727 3.613979634 2.305138535 3.739278006 0.592075345 0.715431142 3.684210702 2.112495277 0.580185451 2.965083474 6.570303675 5.382129144 3.221229118 1.867154482 ...
result:
Subtask #8:
score: 0
Skipped
Dependency #2:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #4:
0%