QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799344#667. Randomized Binary Search TreeKazemaruAC ✓1543ms16420kbC++171.6kb2024-12-05 11:26:332024-12-05 11:26:34

Judging History

This is the latest submission verdict.

  • [2024-12-05 11:26:34]
  • Judged
  • Verdict: AC
  • Time: 1543ms
  • Memory: 16420kb
  • [2024-12-05 11:26:33]
  • Submitted

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,V=1e9;
namespace Kazemaru{
int a1[N],a2[N],a3[N],b1[N],r[N],mo,m2,m3;
#define h(a,b,c,d) for(int a=b;a<c;a+=d)
inline int ksm(int x,int p=mo-2,int y=1){for(;p;p/=2,x=x*x%mo)if(p&1)y=x*y%mo;return y;}
inline int Add(int x,int y){return (x+=y)>=mo?x-mo:x;}
inline void NTT(int*f,int n,int m,int p){
	int k,g,u,v,w,len,ny=ksm(n);
	h(i,0,n,1)if(i<r[i])swap(f[i],f[r[i]]);
	h(l,1,n,l){
		len=l*2;k=len/2;g=ksm(p?m2:m3,(mo-1)/len);
		h(i,0,n*(w=1),len)h(j,0,k,1){
			u=f[i+j];v=f[i+j+k]*w%mo;
			f[i+j]=Add(u,v);f[i+j+k]=Add(u-v,mo);
			w=w*g%mo;
		}
	}
	if(p)h(i,0,n,1)f[i]=f[i]*ny%mo;
}
inline void mul(int*a,int*b,int n,int m){NTT(a,n,m,0);NTT(b,n,m,0);f(i,0,n)a[i]=a[i]*b[i]%mo;NTT(a,n,m,1);}
inline void mul_any(int*a,int*b,int s,int l){
	int p1=998244353,p2=1004535809,p3=469762049;
	__int128 _=1,c1,c2,c3,u=_*p1*p2*p3;
	int n=2,m=0;for(;n<=s+l;n*=2)++m;
	f(i,s+1,n)a[i]=0;f(i,l+1,n)b[i]=0;
	h(i,0,n,1)r[i]=i?(r[i>>1]>>1)|((i&1)<<m):0;
	mo=p1;m2=ksm(m3=3);c1=_*p2*p3*ksm(p2*p3%mo);
	f(i,0,n)a1[i]=a[i],b1[i]=b[i];mul(a1,b1,n,m);
	mo=p2;m2=ksm(m3=3);c2=_*p1*p3*ksm(p1*p3%mo);
	f(i,0,n)a2[i]=a[i],b1[i]=b[i];mul(a2,b1,n,m);
	mo=p3;m2=ksm(m3=3);c3=_*p1*p2*ksm(p1*p2%mo);
	f(i,0,n)a3[i]=a[i],b1[i]=b[i];mul(a3,b1,n,m);
	f(i,0,n)a[i]=(a1[i]*c1+a2[i]*c2+a3[i]*c3)%u/V;
}
#undef h
}
int f[N],g[N],h[N];
signed main(){
	cin>>n;f[0]=V;
	f(p,1,n){
		if(p>50){h[p]=V;continue;}
		f(i,0,n)g[i]=f[i];
		Kazemaru::mul_any(g,g,n,n);
		f(i,1,n)f[i]=g[i-1]/i;h[p]=f[n];
	}
	f(p,1,n)printf("%.5lf\n",(h[p]-h[p-1])*1e-9);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14132kb

input:

1

output:

1.00000

result:

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

Test #2:

score: 0
Accepted
time: 2ms
memory: 13956kb

input:

2

output:

0.00000
1.00000

result:

ok 2 numbers

Test #3:

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

input:

3

output:

0.00000
0.33333
0.66667

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 14224kb

input:

4

output:

0.00000
0.00000
0.66667
0.33333

result:

ok 4 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 14300kb

input:

5

output:

0.00000
0.00000
0.33333
0.53333
0.13333

result:

ok 5 numbers

Test #6:

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

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: 0ms
memory: 13992kb

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: 13992kb

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: 14164kb

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: 0
Accepted
time: 2ms
memory: 14000kb

input:

10

output:

0.00000
0.00000
0.00000
0.06984
0.41557
0.35206
0.13201
0.02734
0.00303
0.00014

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 1543ms
memory: 14748kb

input:

30000

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00030
0.00559
0.03472
0.10051
0.17051
0.19858
0.17720
0.13067
0.08...

result:

ok 30000 numbers

Test #12:

score: 0
Accepted
time: 4ms
memory: 14016kb

input:

56

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00001
0.00660
0.09098
0.24454
0.28157
0.20094
0.10628
0.04550
0.01650
0.00519
0.00144
0.00036
0.00008
0.00002
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 56 numbers

Test #13:

score: 0
Accepted
time: 6ms
memory: 14140kb

input:

154

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00002
0.00314
0.04496
0.15814
0.24546
0.23170
0.15927
0.08826
0.04177
0.01746
0.00657
0.00226
0.00071
0.00021
0.00006
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 154 numbers

Test #14:

score: 0
Accepted
time: 9ms
memory: 14228kb

input:

230

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00081
0.01987
0.10226
0.20879
0.24088
0.19301
0.12121
0.06402
0.02966
0.01236
0.00470
0.00165
0.00054
0.00017
0.00005
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 230 numbers

Test #15:

score: 0
Accepted
time: 9ms
memory: 14236kb

input:

198

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00006
0.00538
0.05505
0.16647
0.24199
0.22307
0.15300
0.08563
0.04126
0.01767
0.00685
0.00244
0.00080
0.00025
0.00007
0.00002
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 198 numbers

Test #16:

score: 0
Accepted
time: 17ms
memory: 14280kb

input:

274

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00004
0.00370
0.04219
0.14238
0.22789
0.22779
0.16740
0.09966
0.05090
0.02309
0.00950
0.00360
0.00126
0.00041
0.00013
0.00004
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 274 numbers

Test #17:

score: 0
Accepted
time: 33ms
memory: 14376kb

input:

657

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00004
0.00264
0.02985
0.11032
0.19873
0.22362
0.18367
0.12142
0.06865
0.03449
0.01577
0.00667
0.00263
0.00098
0.00034
0.00011
0.00004
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 657 numbers

Test #18:

score: 0
Accepted
time: 26ms
memory: 14360kb

input:

628

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00009
0.00435
0.03969
0.12750
0.20918
0.22085
0.17348
0.11099
0.06120
0.03012
0.01353
0.00563
0.00219
0.00080
0.00028
0.00009
0.00003
0.00001
0.00000
0.00000
0.00000
0.00000
0.00000
0.00...

result:

ok 628 numbers

Test #19:

score: 0
Accepted
time: 72ms
memory: 14156kb

input:

1319

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00037
0.00849
0.05287
0.13938
0.20740
0.20994
0.16315
0.10522
0.05920
0.03000
0.01397
0.00607
0.00248
0.00096
0.00035
0.00012
0.00004
0.00001
0.00000
0.00000
0.00...

result:

ok 1319 numbers

Test #20:

score: 0
Accepted
time: 72ms
memory: 16420kb

input:

1453

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00008
0.00326
0.03036
0.10488
0.18767
0.21582
0.18358
0.12650
0.07487
0.03953
0.01907
0.00854
0.00359
0.00142
0.00054
0.00019
0.00007
0.00002
0.00001
0.00000
0.00...

result:

ok 1453 numbers

Test #21:

score: 0
Accepted
time: 67ms
memory: 14372kb

input:

1095

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00009
0.00383
0.03437
0.11387
0.19587
0.21754
0.17950
0.12041
0.06953
0.03585
0.01689
0.00739
0.00303
0.00117
0.00043
0.00015
0.00005
0.00002
0.00000
0.00000
0.00000
0.00...

result:

ok 1095 numbers

Test #22:

score: 0
Accepted
time: 760ms
memory: 14508kb

input:

15826

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00004
0.00171
0.01723
0.06900
0.14547
0.19600
0.19285
0.15182
0.10175
0.06053
0.03287
0.01...

result:

ok 15826 numbers

Test #23:

score: 0
Accepted
time: 724ms
memory: 14048kb

input:

12332

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00004
0.00163
0.01696
0.06894
0.14622
0.19718
0.19363
0.15188
0.10132
0.05996
0.03237
0.01625
0.00...

result:

ok 12332 numbers

Test #24:

score: 0
Accepted
time: 337ms
memory: 14220kb

input:

7285

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00005
0.00196
0.01958
0.07626
0.15535
0.20207
0.19229
0.14673
0.09549
0.05522
0.02916
0.01432
0.00662
0.00290
0.00...

result:

ok 7285 numbers

Test #25:

score: 0
Accepted
time: 337ms
memory: 14480kb

input:

7621

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00002
0.00115
0.01409
0.06315
0.14185
0.19763
0.19744
0.15605
0.10423
0.06149
0.03300
0.01642
0.00768
0.00340
0.00...

result:

ok 7621 numbers

Test #26:

score: 0
Accepted
time: 1533ms
memory: 14796kb

input:

27875

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00002
0.00081
0.01054
0.05088
0.12342
0.18474
0.19684
0.16477
0.11593
0.07...

result:

ok 27875 numbers

Test #27:

score: 0
Accepted
time: 1541ms
memory: 14456kb

input:

29438

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00039
0.00664
0.03853
0.10642
0.17459
0.19856
0.17419
0.12685
0.08...

result:

ok 29438 numbers

Test #28:

score: 0
Accepted
time: 1542ms
memory: 14612kb

input:

29062

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00001
0.00047
0.00744
0.04127
0.11044
0.17720
0.19837
0.17206
0.12427
0.07...

result:

ok 29062 numbers

Test #29:

score: 0
Accepted
time: 1543ms
memory: 14676kb

input:

29415

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00001
0.00040
0.00669
0.03870
0.10666
0.17475
0.19855
0.17406
0.12669
0.08...

result:

ok 29415 numbers

Test #30:

score: 0
Accepted
time: 1531ms
memory: 14756kb

input:

29394

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00001
0.00040
0.00673
0.03885
0.10688
0.17490
0.19854
0.17394
0.12655
0.08...

result:

ok 29394 numbers

Test #31:

score: 0
Accepted
time: 1540ms
memory: 16128kb

input:

29485

output:

0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00000
0.00039
0.00655
0.03820
0.10592
0.17425
0.19857
0.17445
0.12717
0.08...

result:

ok 29485 numbers