QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200298 | #7343. Bicycle Race | SolitaryDream# | WA | 1ms | 3828kb | C++20 | 2.7kb | 2023-10-04 16:19:33 | 2023-10-04 16:19:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pdd=pair<double,double>;
using pvi=pair<vector<int>,int>;
map<pvi, pdd>dp;
int n,k;
double p;
pdd operator +(const pdd &a,const pdd &b)
{
return {a.first+b.first,a.second+b.second};
}
pdd operator *(const pdd &a,const double &b)
{
return {a.first*b,a.second*b};
}
pdd max(const pdd &a,const pdd &b)
{
return {min(a.first,b.first),max(a.first,a.second)};
}
pdd dfs(pvi sta)
{
if(dp.count(sta))
return dp[sta];
auto &ret=dp[sta];
auto [v,x]=sta;
int s=0;
for(auto w:v)
s+=w;
if(s==1)
return ret={1.0,1.0};
vector<int> nv(k);
int con=0;
for(int i=0;i<k;i++)
{
if(i!=x)
{
con+=v[i]>>1;
nv[i]+=v[i]-(v[i]>>1);
if(i+1<k)
nv[i+1]+=v[i]>>1;
}
}
//solve x
if(v[x]%2==0)
{
if(x+1<k)
nv[x+1]+=v[x]>>1;
nv[x]+=v[x]>>1;
con+=v[x]>>1;
ret=ret+dfs({nv,x})*p;
if(x+1<k)
ret=ret+dfs({nv,x+1})*(1-p);
}
else
{
con+=v[x]>>1;
if(x+1<k)
nv[x+1]+=v[x]>>1;
nv[x]+=v[x]-(v[x]>>1);
if(con)
{
ret=(ret+dfs({nv,x})*(p*(1-1.0/v[x])+1.0/v[x]));
if(x+1<k)
ret=(ret+dfs({nv,x+1})*((1-p)*(1-1.0/v[x])));
}
else
{
int A=-1,B=-1;
for(int i=0;i<k;i++)
{
if(v[i])
A=i,B=A;
if(B!=-1)
break;
}
//A fight B
if(A==x||B==x)
{
//x win
auto rem=nv;
nv[A^B^x]--;
if((A^B^x)+1<k)
nv[(A^B^x)+1]++;
ret=(ret+dfs({nv,x})*p);
nv=rem;
nv[x]--;
if(x+1<k)
nv[x+1]++;
if(x+1<k)
ret=(ret+dfs({nv,x+1})*(1-p));
}
else
{
auto rem=nv;
nv[A]--;
if((A)+1<k)
nv[A+1]++;
auto r1=dfs({nv,x});
nv=rem;
nv[B]--;
if(B+1<k)
nv[B+1]++;
auto r2=dfs({nv,x});
ret=(ret+max(r1,r2));
}
}
}
return ret;
}
int main()
{
cin>>n>>k>>p;
vector<int> v(k);
v[0]=n;
pdd ans=dfs({v,0});
printf("%.10lf %.10lf\n",ans.first,ans.second);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3828kb
input:
6 9 1 2 3 2 3 1 3 4 2 4 5 1 3 5 7 2 5 2 1 5 3 4 6 2 5 6 1
output:
0.0000000000 0.0000000000
result:
wrong output format Expected integer, but "0.0000000000" found