QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765973 | #8037. Gambler's Ruin | ericmegalovania | WA | 406ms | 97308kb | C++20 | 1.9kb | 2024-11-20 15:50:11 | 2024-11-20 15:50:12 |
Judging History
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'