QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#58544#4228. Double SortxiaoyaowudiWA 5ms8412kbC++17837b2022-10-26 20:22:282022-10-26 20:22:30

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-26 20:22:30]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 8412kb
  • [2022-10-26 20:22:28]
  • Submitted

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'