QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #765967 | #8037. Gambler's Ruin | ericmegalovania | WA | 1ms | 3940kb | C++20 | 2.2kb | 2024-11-20 15:49:32 | 2024-11-20 15:49:36 |
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;
using PDL=pair<LD,LL>;
const LD eps=1e-6;
inline int sign(const LD& x){
if(fabs(x)<eps) return 0;
return x>LD(0.0)?1:-1;
}
inline int dcmp(const LD& x,const LD& y){
return sign(x-y);
}
int main(){
// freopen("D.in","r",stdin);
// freopen("D.out","w",stdout);
FAST_IO;
int n=read();
vector<PDL>a(n),aa;
for(auto& [p,c]:a){
cin>>p>>c;
}
sort(all(a),[&](const PDL& A,const PDL& B)->bool{
return dcmp(A.first,B.first)==1;
});
aa.push_back(a[0]);
for(int i=1;i<n;i++){
if(!dcmp(a[i].first,aa.back().first)){
aa.back().second+=a[i].second;
}
else{
aa.push_back(a[i]);
}
}
swap(a,aa);
n=a.size();
vector<LL>b(n);
for(int i=0;i<n;i++){
b[i]=(i?b[i-1]:0ll)+a[i].second;
}
auto get=[&](int l,int r){
if(l) return b[r]-b[l-1];
return b[r];
};
LD ans=0.0;
for(int i=0;i<n;i++){
LD x=LD(1.0)/a[i].first;
LL sx=get(0,i);
int l=i+1,r=n-1,mid,opt=-1;
while(l<=r){
mid=l+r>>1;
LD y=LD(1.0)/(LD(1.0)-a[mid].first);
LD sy=get(mid,n-1);
if(y*sy<=x*sx){
opt=mid;
r=mid-1;
ans=fmax(ans,-x*sx+sx+sy);
}
else l=mid+1;
}
if(opt==-1) opt=n;
if(opt-1>i){
// if(opt!=-1 && opt!=i){
--opt;
LD y=LD(1.0)/(LD(1.0)-a[opt].first);
LL sy=get(opt,n-1);
ans=fmax(ans,-y*sy+sx+sy);
}
}
cout<<fixed<<setprecision(12)<<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: 1ms
memory: 3900kb
input:
2 1 15 0 10
output:
10.000000000000
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.333333333333
result:
ok found '33.3333333', expected '33.3333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
1 0 1
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
2 1 0 1 100
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
1 0.5 100
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 0.4 100 0.6 100 0.6 100
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
3 0.2 100 0.2 100 0.8 100
output:
50.000000000000
result:
ok found '50.0000000', expected '50.0000000', error '0.0000000'
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 3940kb
input:
2 0.999999 1000000 0.999998 2
output:
0.000000000000
result:
wrong answer 1st numbers differ - expected: '0.9999990', found: '0.0000000', error = '0.9999990'