QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#756052 | #8037. Gambler's Ruin | bruteforce_ | WA | 0ms | 4072kb | C++20 | 1.6kb | 2024-11-16 18:51:04 | 2024-11-16 18:51:04 |
Judging History
answer
#include<bits/stdc++.h>
#define double long double
using namespace std;
const double eps=1e-15;
struct node
{
double p,v;
int id;
node()
{
p=v=id=0;
}
node(double a,double b,int c)
{
p=a; v=b; id=c;
}
bool operator < (const node &t)
{
return p>t.p;
}
};
void O_o()
{
int n;
cin>>n;
// vector<int> t(n+1);
vector<array<double,2>> a(n+1);
int cnt=0;
a[0][0]=2;
for(int i=1; i<=n; i++)
{
double x,y;
cin>>x>>y;
if(x<=eps)
x+=eps;
else if(1-x<=eps)
x-=eps;
if(fabs(x-a[cnt][0])<=eps)
{
a[cnt][1]+=y;
}
else
{
a[++cnt]={x,y};
}
}
a.resize(cnt+1);
sort(a.begin()+1,a.end(),greater<>());
n=a.size()-1;
vector<node> b(n+1);
for(int i=1; i<=n; i++)
{
b[i]=node(1.0-a[i][0],a[i][1],i);
}
sort(b.begin()+1,b.end());
vector<int> pos(n+1);
for(int i=1; i<=n; i++)
pos[b[i].id]=i;
vector<bool> del(n+1);
int r=1;
double x=0,y=0,sx=0,sy=0;
vector<int> st;
double ans=0;
for(int i=1; i<=n; i++)
{
x=1.0/a[i][0];
sx+=a[i][1];
if(pos[i]<r)
sy-=a[i][1];
del[pos[i]]=1;
while(r<=n&&((sy+b[i].v)*(1.0/b[i].p)<=sx*x||del[r]))
{
if(!del[r])
{
sy+=b[r].v;
st.push_back(r);
}
r++;
}
while(st.size()&&del[st.back()])
st.pop_back();
y=(st.empty()?0:(1.0/b[st.back()].p));
ans=max(ans,sx+sy-max(sx*x,sy*y));
if(r<=n&&(!del[r]))
ans=max(ans,sx+sy+b[r].v-max(sx*x,(sy+b[r].v)*(1.0/b[r].p)));
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(12);
int T=1;
// cin>>T;
while(T--)
{
O_o();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
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: 3828kb
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: 4064kb
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: 4072kb
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: 3892kb
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: 3848kb
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: 3776kb
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: 0
Accepted
time: 0ms
memory: 3964kb
input:
2 0.999999 1000000 0.999998 2
output:
0.999998999999
result:
ok found '0.9999990', expected '0.9999990', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 0 100000 0.000001 1
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3896kb
input:
2 0 1000000000 0.000001 1
output:
0.999998999934
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '0.9999990', error = '0.0000010'