QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54925 | #4228. Double Sort | KING_UT# | AC ✓ | 89ms | 20216kb | C++20 | 1.1kb | 2022-10-11 17:32:36 | 2022-10-11 17:32:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
const int nmax=55;
const int mmax=10005;
using ld=long double;
ld bin[nmax][nmax];
ld dp[nmax][mmax],eq[nmax][mmax];
ld ans[mmax];
void slv(){
int n,m;cin>>n>>m;
m-=n;
bin[0][0]=1;
rep(i,n+1)rep(j,n+1){
if(i)bin[i][j]+=bin[i-1][j];
if(j)bin[i][j]+=bin[i][j-1];
}
rep(i,n+1)rep(j,n+1){
rep(k,j){
bin[i][j]*=(i+k+1);
bin[i][j]/=(m+n)-(i+k);
}
}
rng(i,1,n+1)dp[i][0]=bin[0][i];
rng(i,1,n+1)rep(j,m-i+1){
rng(k,i,n+1){
dp[k][j+i]+=dp[i][j]*bin[i][k-i];
}
}
rep(i,m+1)eq[n][i]=1;
gnr(i,1,n+1)per(j,m-i+1){
rng(k,i,n+1){
eq[i][j]+=eq[k][j+i]*bin[i][k-i];
}
}
rng(i,1,n+1)rep(j,m-i+1){
ld w=0;
rng(k,i,n+1){
w+=eq[k][j+i]*bin[i][k-i];
}
ans[n-i]+=w*dp[i][j];
}
rep(i,n-1)ans[i+1]+=ans[i];
rep(i,n)ans[i]+=1;
rep(i,n-1)ans[i+1]+=ans[i];
rep(i,n)cout<<ans[i]<<endl;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7876kb
input:
3 5
output:
1.00000000000000000000 2.29999999999999999996 4.50000000000000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 3ms
memory: 7832kb
input:
5 17
output:
1.13138332255979314801 2.74838396897220426643 5.18309631544925662576 8.85568842921784098263 15.00000000000000000000
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 89ms
memory: 20216kb
input:
50 10000
output:
4.43281643353642924605 12.83659686678624083783 25.31526873389660153499 41.95561123829224818571 62.84807606175868663692 88.08715467575721323745 117.77163377880214473192 152.00489477779716000760 190.89524200357733471622 234.55626292508845626150 283.10722438472381543018 336.67350947320454665479 395.387...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 6ms
memory: 7944kb
input:
40 40
output:
1.00000000000000000000 2.00000000000000000000 3.00000000000000000000 4.00000000000000000000 5.00000000000000000000 6.00000000000000000000 7.00000000000000000000 8.00000000000000000000 9.00000000000000000000 10.00000000000000000000 11.00000000000000000000 12.00000000000000000000 13.000000000000000000...
result:
ok 40 numbers
Test #5:
score: 0
Accepted
time: 8ms
memory: 9520kb
input:
39 1489
output:
1.52708756282063701139 3.93901256521392071253 7.34033024352952002348 11.76349374502898187302 17.23670136296627585469 23.79071092050161145316 31.45828771293961443299 40.27423309031799695049 50.27559104731479331166 61.50187530303240297791 73.99532469669294276748 87.80119512643682561787 102.96809477877...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 81ms
memory: 19660kb
input:
47 9871
output:
4.88391758536628627432 14.20932202164489387575 28.09393480587513489827 46.64143097166726158534 69.96023578068731913621 98.16395174340850385969 131.37172304640639923512 169.70865107326744256055 213.30625266305588266791 262.30296659374342857496 316.84471482048952131749 377.08552607374023171727 443.188...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 6ms
memory: 7868kb
input:
9 9999
output:
111.55622255525582869201 348.04926039447652430514 727.32800179855393879480 1273.19006403006417071921 2018.95211125406978980301 3014.58913971869464187847 4343.39280983747847253440 6171.94644243750076917365 9000.00000000000000266454
result:
ok 9 numbers