QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661861 | #8037. Gambler's Ruin | inoader | AC ✓ | 477ms | 19608kb | C++14 | 1.1kb | 2024-10-20 18:35:05 | 2024-10-20 18:35:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
inline int read(){
int x=0,k=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')k=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
const int N=1e6+5;
const double eps=1e-13;
int n;
struct node{
double p;
int c;
}a[N];
bool cmp(node x,node y){
return x.p>y.p;
}
void sol(){
n=read();
for(int i=1;i<=n;++i){
cin>>a[i].p;
a[i].c=read();
}
sort(a+1,a+1+n,cmp);
int sx=0;
double ans=0;
int r=n;
int sy=0;
double y=1;
for(int i=1;i<=n;++i){
while(i>r){
sy-=a[r+1].c;
y=1/(1-a[r+1].p);
++r;
}
sx+=a[i].c;
if(a[i].p==a[i+1].p)continue;
double x=1/a[i].p;
while(r>i){
int rr=r;
int ssy=sy+a[rr].c;
while(a[rr-1].p==a[rr].p)ssy+=a[--rr].c;
double yy=1/(1-a[rr].p);
if(ssy-max(sx*x,ssy*yy)>=sy-max(sx*x,sy*y))sy=ssy,y=yy,r=rr-1;
else break;
}
ans=max(ans,sx+sy-max(sx*x,sy*y));
}
printf("%.10f\n",ans);
}
signed main(){
int T=1;
while(T--)sol();
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
2 1 15 0 10
output:
10.0000000000
result:
ok found '10.0000000', expected '10.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
3 0.4 100 0.5 100 0.6 100
output:
33.3333333333
result:
ok found '33.3333333', expected '33.3333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
1 0 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 1 0 1 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
1 0.5 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
3 0.4 100 0.6 100 0.6 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
3 0.2 100 0.2 100 0.8 100
output:
50.0000000000
result:
ok found '50.0000000', expected '50.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
2 0.999999 1000000 0.999998 2
output:
0.9999990000
result:
ok found '0.9999990', expected '0.9999990', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
2 0 100000 0.000001 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
2 0 1000000000 0.000001 1
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 463ms
memory: 19400kb
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:
85718080941203.0625000000
result:
ok found '85718080941203.0625000', expected '85718080941203.0156250', error '0.0000000'
Test #12:
score: 0
Accepted
time: 418ms
memory: 19552kb
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:
86000987369343.9062500000
result:
ok found '86000987369343.9062500', expected '86000987369343.9218750', error '0.0000000'
Test #13:
score: 0
Accepted
time: 404ms
memory: 19416kb
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:
90690663939242.5312500000
result:
ok found '90690663939242.5312500', expected '90690663939242.5468750', error '0.0000000'
Test #14:
score: 0
Accepted
time: 477ms
memory: 19596kb
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:
16307385621417.6093750000
result:
ok found '16307385621417.6093750', expected '16307385621417.6074219', error '0.0000000'
Test #15:
score: 0
Accepted
time: 476ms
memory: 19404kb
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:
38012397725371.2031250000
result:
ok found '38012397725371.2031250', expected '38012397725371.1953125', error '0.0000000'
Test #16:
score: 0
Accepted
time: 436ms
memory: 19552kb
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:
18011656371809.6718750000
result:
ok found '18011656371809.6718750', expected '18011656371809.6757812', error '0.0000000'
Test #17:
score: 0
Accepted
time: 467ms
memory: 19540kb
input:
1000000 0.319563 16045815 0.898271 42370223 0.026295 36626864 0.009444 366071738 0.204970 43180228 0.686325 9473412 0.027009 25042313 0.659717 39445987 0.258480 45282965 0.472879 23682796 0.282075 8710935 0.512861 44842140 0.884086 10841294 0.600897 35981067 0.849081 41822205 0.643385 44337405 0.898...
output:
5561235835638.1347656250
result:
ok found '5561235835638.1347656', expected '5561235835638.1347656', error '0.0000000'
Test #18:
score: 0
Accepted
time: 432ms
memory: 19412kb
input:
1000000 0.253950 46 0.559560 542 0.009900 32083 0.403350 413 0.263990 425 0.921800 698 0.783520 455 0.530070 967 0.213120 478 0.050290 874 0.080430 599 0.992630 64 0.820820 475 0.595230 539 0.592450 290 0.393920 657 0.829040 339 0.831190 655 0.634960 910 0.991650 788 0.171040 707 0.599630 505 0.9605...
output:
1639467837.6792602539
result:
ok found '1639467837.6792603', expected '1639467837.6792715', error '0.0000000'
Test #19:
score: 0
Accepted
time: 463ms
memory: 19404kb
input:
1000000 0.898172 7258266 0.104763 240434786 0.719320 63025017 0.422009 267258882 0.358730 246736331 0.183381 333433297 0.156389 498175665 0.797353 4106581 0.176858 677562755 0.519227 23114268 0.813408 17408292 0.661235 68857040 0.579091 35432878 0.451862 60091054 0.851985 8763380 0.508252 72544830 0...
output:
20717770537103.9218750000
result:
ok found '20717770537103.9218750', expected '20717770537103.9140625', error '0.0000000'
Test #20:
score: 0
Accepted
time: 473ms
memory: 19608kb
input:
1000000 0.506643 11838878 0.022718 7 0.215186 49647 0.189161 41240 0.601065 47155106 0.617912 38963493 0.924862 187751265 0.570828 34596465 0.296104 606617 0.819090 181192827 0.541691 22738007 0.978440 701932225 0.678464 39014036 0.879408 0 0.289540 589194 0.360810 1544441 0.335420 142408 0.749706 1...
output:
6131806884974.7578125000
result:
ok found '6131806884974.7578125', expected '6131806884974.7607422', error '0.0000000'
Test #21:
score: 0
Accepted
time: 446ms
memory: 19416kb
input:
1000000 0.268276 9 0.483196 7 0.131214 2 0.937202 2 0.227950 2 0.707708 1 0.776346 7 0.031180 4 0.651482 10 0.359102 9 0.455016 9 0.302518 2 0.270340 7 0.500180 2 0.602974 2 0.409752 5 0.949974 8 0.425086 3 0.978080 0 0.764962 5 0.793300 5 0.802016 6 0.871474 3 0.007990 5 0.681198 4 0.040534 2 0.667...
output:
4981943.0000000000
result:
ok found '4981943.0000000', expected '4981943.0000000', error '0.0000000'
Test #22:
score: 0
Accepted
time: 456ms
memory: 19420kb
input:
1000000 0.119382 617256 0.363456 4259814 0.241892 8125466 0.349642 1231977 0.178516 3859513 0.839628 6794539 0.787806 9774871 0.069012 3739020 0.959006 9910122 0.036676 6096603 0.016698 1864421 0.309786 3306756 0.695128 7551944 0.874058 406134 0.196980 8336449 0.277616 5104388 0.292342 6722343 0.392...
output:
861363030857.9038085938
result:
ok found '861363030857.9038086', expected '861363030857.9036865', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
1000 0.409000 51 0.119000 84 0.191000 34 0.686000 95 0.348000 1 0.308000 47 0.355000 85 0.896000 7 0.310000 52 0.053000 28 0.542000 5 0.621000 58 0.583000 16 0.856000 61 0.145000 88 0.628000 85 0.647000 38 0.951000 77 0.285000 96 0.889000 28 0.168000 59 0.053000 33 0.848000 16 0.195000 57 0.142000 3...
output:
8781.9645390071
result:
ok found '8781.9645390', expected '8781.9645390', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed