QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#58543 | #4228. Double Sort | xiaoyaowudi | WA | 5ms | 8536kb | C++17 | 782b | 2022-10-26 20:19:08 | 2022-10-26 20:19:11 |
Judging History
answer
#include <iostream>
#include <algorithm>
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;
}
}
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: 8536kb
input:
3 5
output:
1 2.3 4.5
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 8464kb
input:
5 17
output:
1.13138 2.74838 5.1831 8.85569 15
result:
wrong answer 1st numbers differ - expected: '1.1313833', found: '1.1313800', error = '0.0000029'