QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#58544 | #4228. Double Sort | xiaoyaowudi | WA | 5ms | 8412kb | C++17 | 837b | 2022-10-26 20:22:28 | 2022-10-26 20:22:30 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <iomanip>
constexpr int M=10010,N=60;
typedef double lf;
lf comb[M][N];
int main(){
comb[0][0]=1;
for(int i=1;i<M;++i)
{
comb[i][0]=1;
for(int j=1;j<=i && j<N;++j) comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
}
int n,m;
std::cin>>n>>m;
lf tot=comb[m][n];
static lf ans[N];
for(int i=1;i<=n;++i)
{
static lf G[N];
for(int k=i;k<=n;++k)
{
lf cur=1;
for(int j=i;j<k;++j) cur-=comb[k][j]*G[j];
G[k]=cur;
}
for(int j=1;i*j+n-i<=m;++j)
{
lf cur=0;
for(int k=i;k<=n;++k)
{
int sum=m-k*(j-1);
if(sum>0) cur+=G[k]*comb[n][k]*comb[sum][n];
}
ans[n-i+1]+=cur/tot;
}
}
std::cout<<std::setprecision(8);
for(int i=1;i<=n;++i) ans[i]+=ans[i-1],std::cout<<ans[i]<<" ";
std::cout<<std::endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 8396kb
input:
3 5
output:
1 2.3 4.5
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 5ms
memory: 8384kb
input:
5 17
output:
1.1313833 2.748384 5.1830963 8.8556884 15
result:
ok 5 numbers
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 8412kb
input:
50 10000
output:
4.4328164 12.836597 25.315269 41.955611 62.848076 88.087155 117.77163 152.00489 190.89525 234.55627 283.10763 336.67294 395.39363 459.39371 529.09942 599.49514 658.40309 443.774 2325.9007 2366.8649 6995.5905 19889.104 2011.3454 11735.383 -114520.96 190407.82 3267629.8 6208712.8 4284428.6 2976845.1 3...
result:
wrong answer 11th numbers differ - expected: '283.1072244', found: '283.1076300', error = '0.0000014'