QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412928 | #6565. Game Show Elimination | grass8cow | AC ✓ | 65ms | 66132kb | C++17 | 3.2kb | 2024-05-16 21:45:26 | 2024-05-16 21:45:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define db double
int m,e;
ll f[12];
vector<db>sol(vector<int>l){
vector<db>an;
int n=l.size();for(int i=0;i<n;i++)an.pb(0);
for(int i=0;i<n;i++){
for(int d=l[i];d<l[i]+m;d++){
for(int j=0;j<n;j++)if(i!=j){
if(l[j]+m<=d)continue;
bool fp=0;
for(int k=0;k<n;k++)if(i!=k&&j!=k&&d<l[k]){fp=1;break;}
if(fp)continue;
memset(f,0,sizeof(f));
if(l[j]>d)f[0]=m,e=0;
else f[0]=l[j]+m-d,f[1]=-1,e=1;
for(int k=0;k<n;k++)if(i!=k&&j!=k){
if(l[k]+m<=d){for(int z=0;z<=e;z++)f[z]*=m;}
else{for(int z=e;z>=0;z--)f[z+1]+=f[z],f[z]*=(d-l[k]);e++;}
}
for(int z=0;z<=e;z++)an[i]+=1.0*f[z]/(z+1);
}
}
}
db P=1;for(int i=1;i<=n;i++)P*=m;
for(db &x:an)x/=P;return an;
}
int n,n_;
const db eps=1e-12;
int pp[(1<<9)+10],lk[(1<<9)+10],sn[1010];
db dp[1010][(1<<9)+10][15],xs[(1<<9)+10][15][15],ans[1010];
int main(){
scanf("%d%d",&n,&m);n_=m-1;
for(int s=1;s<(1<<n_);s++)pp[s]=pp[s>>1]+(s&1),lk[s]=log2(s&-s);
for(int s=0;s<(1<<n_);s++)for(int j=1;j<=m;j++){
vector<int>wx;
for(int i=n_-1;i>=0;i--)if((s>>i)&1)wx.pb(n_-1-i);
wx.pb(n_),wx.pb(n_+j);
vector<db>ww=sol(wx);
int e=0;
for(int i=n_-1;i>=0;i--)if((s>>i)&1)xs[s][j][i]=ww[e++];
xs[s][j][n_]=ww[e++];
xs[s][j][n_+1]=ww[e++];
}
for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(i>j)sn[i]|=(1<<(j-1));
dp[n-1][sn[n-1]][1]=1;
for(int i=n-1;i;i--)for(int s=(1<<n_)-1;s>=0;s--)for(int j=1;j<=m;j++){
if(dp[i][s][j]<eps)continue;
db jb=dp[i][s][j];
int R=max(0,i-m)+pp[s]+1;
for(int k=0;k<n_;k++)if((s>>k)&1){
db ox=jb*xs[s][j][k];
dp[i][s^(1<<k)][j]+=ox;
//assert(i-1-k>0);
ans[i-1-k]+=ox*R;
}
if(xs[s][j][n_]>eps){
db ox=jb*xs[s][j][n_];
ans[i]+=ox*R;if(R>1){
if(!s)dp[i-m][sn[i-m]][m]+=ox;
else{
int z=lk[s]+1,s2=0;
for(int j=1;j<=n_;j++){
if(i-z-j<=0)break;
if(z-1+j<n_){if((s>>(z-1+j))&1)s2|=(1<<(j-1));}
else s2|=(1<<(j-1));
}
dp[i-z][s2][min(m,z+j)]+=ox;
}
}
}
if(j<m&&xs[s][j][n_+1]>eps){
db ox=jb*xs[s][j][n_+1];
ans[i+j]+=ox*R;if(R>1){
if(!s)dp[i-m][sn[i-m]][m]+=ox;
else{
int z=lk[s]+1,s2=0;
for(int j=1;j<=n_;j++){
if(i-z-j<=0)break;
if(z-1+j<n_){if((s>>(z-1+j))&1)s2|=(1<<(j-1));}
else s2|=(1<<(j-1));
}
dp[i-z][s2][z]+=ox;
}
}
}
}
for(int i=1;i<=n;i++)printf("%.9lf\n",ans[i]+1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6076kb
input:
3 2
output:
2.109375000 2.625000000 1.265625000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 65ms
memory: 66132kb
input:
1000 10
output:
2.927293246 3.537316064 4.281182083 5.131220508 6.053932593 7.019188288 8.005702141 9.001290736 10.000164877 10.999999632 11.999999596 12.999999559 13.999999522 14.999999485 15.999999449 16.999999412 17.999999375 18.999999339 19.999999302 20.999999265 21.999999229 22.999999192 23.999999155 24.999999...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 11372kb
input:
300 8
output:
2.751263044 3.390073717 4.175006852 5.066021503 6.020146538 7.004557835 8.000572565 8.999999968 9.999999964 10.999999960 11.999999956 12.999999952 13.999999948 14.999999944 15.999999940 16.999999936 17.999999932 18.999999928 19.999999924 20.999999920 21.999999916 22.999999912 23.999999908 24.9999999...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 8236kb
input:
1000 3
output:
2.230256168 3.034765671 4.000000000 5.000000000 6.000000000 7.000000000 8.000000000 9.000000000 10.000000000 11.000000000 12.000000000 13.000000000 14.000000000 15.000000000 16.000000000 17.000000000 18.000000000 19.000000000 20.000000000 21.000000000 22.000000000 23.000000000 24.000000000 25.000000...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 25ms
memory: 6904kb
input:
7 10
output:
2.981586438 3.493604960 3.965342265 4.319677059 4.508724856 4.498880848 4.232183574
result:
ok 7 numbers
Test #6:
score: 0
Accepted
time: 23ms
memory: 38948kb
input:
993 9
output:
2.841121207 3.464359215 4.227324329 5.096942550 6.035281606 7.010574172 8.002387311 9.000302424 9.999999893 10.999999882 11.999999870 12.999999858 13.999999846 14.999999834 15.999999822 16.999999811 17.999999799 18.999999787 19.999999775 20.999999763 21.999999751 22.999999740 23.999999728 24.9999997...
result:
ok 993 numbers