QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799263 | #667. Randomized Binary Search Tree | Kazemaru | WA | 1ms | 8404kb | C++17 | 1.2kb | 2024-12-05 09:44:06 | 2024-12-05 09:44:07 |
Judging History
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 eps=1e-9,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(i,1,n)if(fabs(f[i])<eps)f[i]=0;
}
f(p,1,n)printf("%.5Lf\n",g[p]-g[p-1]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8400kb
input:
1
output:
1.00000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 8404kb
input:
2
output:
0.00000 1.00000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 8224kb
input:
3
output:
0.00000 0.33333 0.66667
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 8320kb
input:
4
output:
0.00000 0.00000 0.66667 0.33333
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 8308kb
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: 8192kb
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: 8324kb
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: 8324kb
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: 8128kb
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: 8248kb
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'