QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114669#5973. Kiddie Poolzwh200825 ✓3ms3684kbC++141.2kb2023-06-22 19:48:582023-06-22 19:48:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-22 19:48:59]
  • 评测
  • 测评结果:25
  • 用时:3ms
  • 内存:3684kb
  • [2023-06-22 19:48:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,Case;
long double V,T;
struct node{long double r,t;}a[N];
bool chk(long double x) {
	long double nv=0,mnt=0,mxt=0;
	for(int i=1;i<=n;i++) {
		long double s=a[i].r*x;
		if(nv+s>V){mnt+=(V-nv)*a[i].t,nv=V;break;}
		else mnt+=s*a[i].t,nv+=s;
	}
	if(nv<V)return 0;
	mnt/=V,nv=0;
	for(int i=n;i;i--) {
		long double s=a[i].r*x;
		if(nv+s>V){mxt+=(V-nv)*a[i].t,nv=V;break;}
		else mxt+=s*a[i].t,nv+=s;
	}mxt/=V;
	return (mnt-T)<=1e-12&&(T-mxt)<=1e-12;
}
void solve() {
	scanf("%d%Lf%Lf",&n,&V,&T);
	for(int i=1;i<=n;i++)scanf("%Lf%Lf",&a[i].r,&a[i].t);
	long double l=0,r=1e8,mid,ans=-1;sort(a+1,a+n+1,[](const node&x,const node&y){return x.t<y.t;});
	for(int i=1;i<=100;i++)mid=(l+r)/2,chk(mid)?r=mid,ans=mid:l=mid;
//	if(Case==11) {
//		printf("%d %Lf %Lf\n",n,V,T);
//		for(int i=1;i<=n;i++)printf("%Lf %Lf\n",a[i].r,a[i].t);
//	}
	if(ans<0)printf("Case #%d: IMPOSSIBLE\n",++Case);
	else printf("Case #%d: %.8Lf\n",++Case,ans);
}
int main() {
	int tt;scanf("%d",&tt);
	while(tt--)solve();
	return 0;
}
/*
1
2 94.770700 60.432300
100.000000 60.432300
99.999900 60.432300
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 1ms
memory: 3628kb

input:

100
2 77.4956 5.3818
0.0004 3.7300
99.9993 5.3818
2 99.9998 49.4406
98.1477 49.4406
99.9997 41.1985
2 99.9990 85.5865
99.9992 66.1663
99.9993 85.5865
2 99.9994 2.2480
99.9994 2.2448
99.9998 51.8149
2 0.0010 91.4534
0.0009 84.1767
99.9991 91.4534
2 0.0009 74.8941
99.9999 65.1204
99.9993 84.6678
2 99....

output:

Case #1: 0.77496142
Case #2: 1.01887054
Case #3: 0.99999700
Case #4: 0.99993544
Case #5: 0.00001000
Case #6: 0.00000450
Case #7: 0.99999900
Case #8: 1.00000000
Case #9: 0.50759777
Case #10: 2.00000000
Case #11: 999999.98999995
Case #12: 0.47385374
Case #13: IMPOSSIBLE
Case #14: 0.00000698
Case #15: ...

result:

ok correct! (100 test cases)

Subtask #2:

score: 18
Accepted

Test #2:

score: 18
Accepted
time: 3ms
memory: 3684kb

input:

100
58 0.0008 99.1595
0.0005 30.5091
0.0008 44.0520
0.0004 40.6945
0.0008 80.0392
0.0003 26.9373
0.0004 25.5406
0.0010 27.1416
0.0011 39.1921
0.0007 9.8981
0.0001 91.7185
0.0010 39.2460
0.0005 96.9054
0.0002 20.9389
0.0011 92.2262
0.0003 64.4162
0.0005 70.7304
0.0007 77.0529
0.0002 64.2427
0.0009 95...

output:

Case #1: 0.31258754
Case #2: IMPOSSIBLE
Case #3: 1.00000000
Case #4: 0.07602348
Case #5: 0.00000000
Case #6: 24999997.74987450
Case #7: 0.08526911
Case #8: 0.00000010
Case #9: 0.50000000
Case #10: 0.02954574
Case #11: IMPOSSIBLE
Case #12: 0.00534134
Case #13: 0.44799209
Case #14: 0.01917417
Case #15...

result:

ok correct! (100 test cases)

Extra Test:

score: 0
Extra Test Passed