QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#711532#6565. Game Show Eliminationucup-team902WA 148ms15220kbC++204.3kb2024-11-05 11:52:572024-11-05 11:52:58

Judging History

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

  • [2024-11-05 11:52:58]
  • 评测
  • 测评结果:WA
  • 用时:148ms
  • 内存:15220kb
  • [2024-11-05 11:52:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using db=double;
const int N=1000,K=1<<9;
const db eps=1e-9;
int n,k;
db g[12][K+5][12],f[N+5][12][K+5];
db ans[N+5];
int getv(int x,int d){
    return x==k?0:x==k+1?d:-x-1;
}
db work(int d,int s,int pos,int mx){
    if(pos==mx) return 0;
    mx=getv(mx,d);
    pos=getv(pos,d);
    // printf("%d %d\n",mx,pos);
    static db h[12];
    db res=0;
    for(int v=pos;v<pos+k;v++){
        memset(h,0,sizeof h);
        h[0]=1;
        for(int i=0;i<=k+1;i++)
            if((s>>i&1)||(i>=k)){
                int vi=getv(i,d);
                if(vi==pos) continue;
                if(vi!=mx){
                    if(v<vi)
                        memset(h,0,sizeof h);
                    else if(v<vi+k){
                        for(int j=k;j;j--)
                            h[j]=h[j-1]+(v-vi)*h[j];
                        h[0]*=(v-vi);
                        for(int j=0;j<=k;j++) h[j]/=k;
                    }
                }
                else{
                    if(v>=vi+k)
                        memset(h,0,sizeof h);
                    else if(v>=vi){
                        for(int j=k;j;j--)
                            h[j]=h[j]*(vi+k-v)-h[j-1];
                        h[0]*=(vi+k-v);
                        for(int j=0;j<=k;j++) h[j]/=k;
                    }
                }
            }
        for(int i=0;i<=k;i++)
            res+=h[i]/(i+1);
        // printf("%lf\n",res);
    }
    return res/k;
}
void prep(){
    for(int i=1;i<=k;i++)
        for(int s=0;s<(1<<k-1);s++){
            for(int j=0;j<=k+1;j++){
                if((s>>j&1)||j>=k){
                    int mx;
                    for(mx=0;mx<k;mx++)
                        if((s>>mx&1)&&(-mx-1+k>i))
                            g[i][s][j]+=work(i,s,j,mx);
                    // if(i==1&&s==1){
                    //     printf("%d %d %d %lf\n",i,s,j,g[i][s][j]);
                    // }
                    g[i][s][j]+=work(i,s,j,k);
                    // if(i==1&&s==1){
                    //     printf("%d %d %d %lf\n",i,s,j,g[i][s][j]);
                    // }
                    g[i][s][j]+=work(i,s,j,k+1);
                    // if(i==1&&s==1){
                    //     printf("%d %d %d %lf\n",i,s,j,g[i][s][j]);
                    // }
                }
            }
        }
}
int popc(int s){
    int res=0;
    for(;s;s&=s-1) res++;
    return res;
}
int main(){
    scanf("%d %d",&n,&k);
    prep();
    f[n-1][1][(1<<min(k-1,n-2))-1]=1;
    for(int i=n-1;i;i--){
        int rk=min(i-1,k-1);
        for(int j=1;j<=k;j++){
            for(int s=(1<<rk)-1;s>=0;s--){
                if(f[i][j][s]<eps) continue;
                int crk=i-rk+1+popc(s);
                // printf("%d %d %d %lf\n",i,j,s,f[i][j][s]);
                // printf("%d %d %d %d\n",i,j,s,crk);
                for(int l=0;l<rk;l++)
                    if(s>>l&1){
                        db c=f[i][j][s]*g[j][s][l];
                        ans[i-l-1]+=c*crk;
                        f[i][j][s^(1<<l)]+=c;
                    }
                if(crk==2){
                    db c1=f[i][j][s]*g[j][s][k];
                    db c2=f[i][j][s]*g[j][s][k+1];
                    ans[i]+=c1*2+c2;
                    if(j<k)
                        ans[i+j]+=c2*2+c1;
                }
                else{
                    int ni=i-1,ns=s|(1<<k);
                    while(1){
                        if(ns&1){
                            ns>>=1;
                            break;
                        }
                        ni--;
                        ns=(ns>>1)|(1<<k);
                    }
                    ns&=(1<<min(ni-1,k-1))-1;
                    db c=f[i][j][s]*g[j][s][k];
                    ans[i]+=c*crk;
                    int nd=i+j-ni;
                    if(j<k&&nd>=k)
                        ans[i+j]+=c;
                    nd=min(nd,k);
                    f[ni][nd][ns]+=c;
                    if(j<k){
                        c=f[i][j][s]*g[j][s][k+1];
                        nd=i-ni;
                        ans[i+j]+=c*crk;
                        f[ni][nd][ns]+=c;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%.13lf\n",ans[i]);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3888kb

input:

3 2

output:

2.1093750000000
2.6250000000000
1.2656250000000

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 148ms
memory: 15220kb

input:

1000 10

output:

1.6337777249909
1.8498476943878
2.1194353886430
2.4355825624524
2.7908622536682
3.1794787362339
3.5988404009317
4.0492873538501
4.5322323145456
5.0481135064904
5.6700220116298
6.2919305167691
6.9138390219085
7.5357475270478
8.1576560321872
8.7795645373265
9.4014730424659
10.0233815476052
10.64529005...

result:

wrong answer 1st numbers differ - expected: '2.9272933', found: '1.6337777', error = '0.4418811'