QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200298#7343. Bicycle RaceSolitaryDream#WA 1ms3828kbC++202.7kb2023-10-04 16:19:332023-10-04 16:19:33

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 16:19:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3828kb
  • [2023-10-04 16:19:33]
  • 提交

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