QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242136#7651. 傅里叶与交通规划youngsystem15 60ms6004kbC++203.2kb2023-11-06 23:18:322023-11-06 23:18:32

Judging History

你现在查看的是最新测评结果

  • [2023-11-06 23:18:32]
  • 评测
  • 测评结果:15
  • 用时:60ms
  • 内存:6004kb
  • [2023-11-06 23:18:32]
  • 提交

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%