QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799258#667. Randomized Binary Search TreeKazemaruWA 1ms8412kbC++171.2kb2024-12-05 09:39:532024-12-05 09:39:54

Judging History

你现在查看的是最新测评结果

  • [2024-12-05 09:39:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8412kb
  • [2024-12-05 09:39:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e5;
#define double long double
const double Pi=acos(-1.0);
struct xy{double x,y;};
inline xy operator+(xy a,xy b){return{a.x+b.x,a.y+b.y};}
inline xy operator-(xy a,xy b){return{a.x-b.x,a.y-b.y};}
inline xy operator*(xy a,xy b){return{a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
int r[N];
#define h(a,b,c,d) for(int a=b;a<c;a+=d)
inline void FFT(xy*a,int n,int p){
	h(i,1,n,1)if(i<r[i])swap(a[i],a[r[i]]);
	xy u,v,w,g;
	h(k,1,n,k){
		g={cos(Pi/k),(p?-1:1)*sin(Pi/k)};
		h(i,0,n,k*2){
			w={1,0};
			h(j,0,k,1){
				u=a[i+j];v=a[i+j+k]*w;w=w*g;
				a[i+j]=u+v;a[i+j+k]=u-v;
			}
		}
	}
	if(p)h(i,0,n,1)a[i].x/=n;
}
inline void sqr(xy*a,int s){
	int n=2,m=0;
	for(;n<=s+s;n*=2)++m;
	h(i,1,n,1)r[i]=(r[i>>1]>>1)|((i&1)<<m);
	f(i,s+1,n)a[i]={};
	FFT(a,n,0);
	f(i,0,n)a[i]=a[i]*a[i];
	FFT(a,n,1);
}
double f[N],g[N];xy a[N];
signed main(){
	cin>>n;f[0]=1;
	f(p,1,n){
		if(p>50){g[p]=1;continue;}
		f(i,0,n)a[i].x=f[i];sqr(a,n);
		f(i,1,n)f[i]=a[i-1].x/i;g[p]=f[n];
	}
	f(p,1,n)printf("%.5Lf\n",g[p]-g[p-1]);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 8412kb

input:

1

output:

1.00000

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 8300kb

input:

2

output:

0.00000
1.00000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 8316kb

input:

3

output:

0.00000
0.33333
0.66667

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 8192kb

input:

4

output:

0.00000
0.00000
0.66667
0.33333

result:

ok 4 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 8320kb

input:

5

output:

0.00000
0.00000
0.33333
0.53333
0.13333

result:

ok 5 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 8356kb

input:

6

output:

0.00000
-0.00000
0.11111
0.55556
0.28889
0.04444

result:

ok 6 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 8408kb

input:

7

output:

0.00000
0.00000
0.01587
0.44444
0.40635
0.12063
0.01270

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 8252kb

input:

8

output:

0.00000
0.00000
0.00000
0.28175
0.46667
0.20714
0.04127
0.00317

result:

ok 8 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 8392kb

input:

9

output:

0.00000
0.00000
0.00000
0.15168
0.46508
0.28783
0.08272
0.01199
0.00071

result:

ok 9 numbers

Test #10:

score: -100
Wrong Answer
time: 1ms
memory: 8196kb

input:

10

output:

0.00000
-0.00000
0.00000
0.06984
0.41557
0.35206
0.13201
0.02734
0.00304
0.02304

result:

wrong answer 10th numbers differ - expected: '0.00014', found: '0.02304', error = '0.02290'