QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#765973#8037. Gambler's RuinericmegalovaniaWA 406ms97308kbC++201.9kb2024-11-20 15:50:112024-11-20 15:50:12

Judging History

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

  • [2024-11-20 15:50:12]
  • 评测
  • 测评结果:WA
  • 用时:406ms
  • 内存:97308kb
  • [2024-11-20 15:50:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

//#define ONLINE
#ifndef ONLINE
char DEBUG_BUFFER[1000];
#define debug(...) {sprintf(DEBUG_BUFFER,##__VA_ARGS__);\
cerr<<"\033[1;36m"<<DEBUG_BUFFER<<"\033[0;2m"<<"\033[0m";}
#else
#define debug(...) ;
#endif

using LL=long long;
using PII=pair<int,int>;

#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()

#define FAST_IO {ios::sync_with_stdio(false);cin.tie(nullptr);}
inline int read(){static int x; cin>>x; return x;}
inline LL readLL(){static LL x; cin>>x; return x;}
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

using LD=long double;
struct node{
	LD p;
	LL c;
};

int main(){
//	freopen("D.in","r",stdin);
//	freopen("D.ans","w",stdout);
	FAST_IO;
	int n=read();
	vector<node>a(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i].p>>a[i].c;
	}
	sort(a.begin()+1,a.end(),[&](auto& l,auto& r)->bool{
		return l.p>r.p;
	});
	int m=1;
	for(int i=2;i<=n;i++){
		if(a[m].p==a[i].p){
			a[m].c+=a[i].c;
		}
		else{
			a[++m]=a[i];
		}
	}
	vector<LD>x(n+2),y(n+2);
	for(int i=1;i<=m;i++){
		x[i]=x[i-1]+a[i].c;
	}
	for(int i=m;i>0;i--){
		y[i]=y[i+1]+a[i].c;
	}
	vector<LD>ans1(n+2),ans2(n+2);
	for(int i=1;i<=m;i++){
		if(a[i].p==0){
			ans1[i]=1e20;
			continue;
		}
		LD p=1.0/a[i].p;
		ans1[i]=p*x[i];
	}
	for(int i=m;i>0;i--){
		if(a[i].p==1){
			ans2[i]=1e20;
			continue;
		}
		LD p=1.0/(1.0-a[i].p);
		ans2[i]=p*y[i];
	}
	LD ans=0.0;
	for(int i=1;i<=m;i++){
		int l=i+1,r=m+1;
		while(l<r){
			int mid=l+r>>1;
			if(ans2[mid]>ans1[i]){
				l=mid+1;
			}
			else r=mid;
		}
		ans=max(ans,x[i]+y[l]-max(ans1[i],ans2[l]));
		if(l>i+1) l--;
		ans=max(ans,x[i]+y[l]-max(ans1[i],ans2[l]));
	}
	cout<<ans;
	return 0;
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3880kb

input:

2
1 15
0 10

output:

10

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

3
0.4 100
0.5 100
0.6 100

output:

33.3333

result:

ok found '33.3333000', expected '33.3333333', error '0.0000010'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

1
0 1

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

2
1 0
1 100

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

1
0.5 100

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

3
0.4 100
0.6 100
0.6 100

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3
0.2 100
0.2 100
0.8 100

output:

50

result:

ok found '50.0000000', expected '50.0000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

2
0.999999 1000000
0.999998 2

output:

0.999999

result:

ok found '0.9999990', expected '0.9999990', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

2
0 100000
0.000001 1

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

2
0 1000000000
0.000001 1

output:

1

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 386ms
memory: 97056kb

input:

1000000
0.375733 595197307
0.505261 377150668
0.517039 15795246
0.448099 228176467
0.529380 871983979
0.905546 876268308
0.095891 272104456
0.500302 916153337
0.128705 355768079
0.070600 78747362
0.444107 466118868
0.194987 298494965
0.462293 593292779
0.287909 838058266
0.237226 934603199
0.391909 ...

output:

8.57181e+13

result:

ok found '85718100000000.0000000', expected '85718080941203.0156250', error '0.0000002'

Test #12:

score: 0
Accepted
time: 325ms
memory: 97088kb

input:

1000000
0.353000 999523129
0.526000 14560746
0.978000 319977952
0.324000 353889639
0.535500 497827437
0.153000 660990580
0.482000 391332319
0.050000 118814686
0.862500 774878817
0.417500 124874110
0.172500 789760737
0.058000 236910286
0.596000 585483625
0.176500 388072811
0.838000 806903092
0.613000...

output:

8.6001e+13

result:

ok found '86001000000000.0000000', expected '86000987369343.9218750', error '0.0000001'

Test #13:

score: 0
Accepted
time: 323ms
memory: 97080kb

input:

1000000
0.200000 715833054
0.250000 346181893
0.700000 84047805
0.225000 911121283
0.575000 349964342
0.200000 472178743
0.400000 487500419
0.775000 358482180
0.525000 282051084
0.475000 664059239
0.350000 143371889
0.075000 768191797
0.025000 892648527
0.250000 266570522
0.175000 590192616
0.775000...

output:

9.06907e+13

result:

ok found '90690700000000.0000000', expected '90690663939242.5468750', error '0.0000004'

Test #14:

score: 0
Accepted
time: 395ms
memory: 97088kb

input:

1000000
0.483249 58806278
0.092943 43698395
0.682093 234500498
0.899881 212323106
0.031970 94677621
0.248163 61052399
0.577708 189447689
0.737973 129234039
0.210538 112081344
0.451271 24559811
0.411130 846942
0.916990 268662655
0.992736 184750465
0.112959 105654084
0.932484 8474182
0.949654 21518817...

output:

1.63074e+13

result:

ok found '16307400000000.0000000', expected '16307385621417.6074219', error '0.0000009'

Test #15:

score: 0
Accepted
time: 406ms
memory: 97308kb

input:

1000000
0.019963 244843587
0.361281 50413366
0.776551 132525209
0.435213 112540619
0.689322 261233354
0.023354 75471114
0.897100 120761316
0.650546 203049584
0.562689 213573846
0.606257 117745257
0.242362 401834266
0.331500 571471418
0.172223 291092482
0.713109 169535508
0.056464 106853676
0.068823 ...

output:

3.80124e+13

result:

ok found '38012400000000.0000000', expected '38012397725371.1953125', error '0.0000001'

Test #16:

score: -100
Wrong Answer
time: 349ms
memory: 97120kb

input:

1000000
0.299950 14454994
0.590800 131103748
0.168700 31811722
0.640950 153861933
0.097300 42347624
0.689900 25513183
0.313950 7694955
0.434400 41038786
0.992950 549929012
0.844350 177512169
0.193800 85807309
0.930300 78556126
0.920950 132277934
0.786750 282121687
0.420200 110220790
0.541000 9878024...

output:

1.80117e+13

result:

wrong answer 1st numbers differ - expected: '18011656371809.6757812', found: '18011700000000.0000000', error = '0.0000024'