QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234645#667. Randomized Binary Search TreePetroTarnavskyi#AC ✓219ms8016kbC++172.2kb2023-11-01 20:14:162023-11-01 20:14:16

Judging History

This is the latest submission verdict.

  • [2023-11-01 20:14:16]
  • Judged
  • Verdict: AC
  • Time: 219ms
  • Memory: 8016kb
  • [2023-11-01 20:14:16]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

typedef complex<db> cmplx;

const db PI = acos(-1.0);
const int N = 1 << 16;

cmplx pw[N];

void initFFT()
{
	db angle = 2 * PI / N;
	FOR(i, 0, N)
		pw[i] = {cos(i * angle), sin(i * angle)};
}

void fft(vector<cmplx>& a, bool inv)
{
	int lg = 0;
	while ((1 << lg) < SZ(a))
		lg++;
	FOR(i, 0, SZ(a))
	{
		int x = 0;
		FOR(j, 0, lg)
			x |= ((i >> j) & 1) << (lg - j - 1);
		if (i < x)
			swap(a[i], a[x]);
	}
	for (int len = 2; len <= SZ(a); len *= 2)
	{
		int diff = inv ? N - N / len : N / len;
		for (int i = 0; i < SZ(a); i += len)
		{
			int pos = 0;
			FOR(j, 0, len / 2)
			{
				cmplx u = a[i + j], v = a[i + j + len / 2] * pw[pos];
				a[i + j] = u + v;
				a[i + j + len / 2] = u - v;
				pos += diff;
				if (pos >= N)
					pos -= N;
			}
		}
	}
	if (inv)
	{
		FOR(i, 0, SZ(a))
			a[i] /= SZ(a);
	}
}

vector<db> mult(const vector<db>& a, const vector<db>& b)
{
	vector<cmplx> ac(ALL(a)), bc(ALL(b));
	int lg = 0;
	while ((1 << lg) < SZ(a) + SZ(b) - 1)
		lg++;
	ac.resize(1 << lg);
	bc.resize(1 << lg);
	fft(ac, false);
	fft(bc, false);
	FOR(i, 0, SZ(ac))
		ac[i] *= bc[i];
	fft(ac, true);
	vector<db> c(SZ(a) + SZ(b) - 1);
	FOR(i, 0, SZ(c))
		c[i] = ac[i].real();
	return c;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(6);
	initFFT();
	int n;
	cin >> n;
	vector<db> ans(n, 1);
	if (n > 1)
		ans[0] = 0;
	vector<db> f = {1, 1};
	FOR(j, 1, min(n, 55))
	{
		vector<db> nf = mult(f, f);
		f.resize(min(n, SZ(nf)) + 1);
		f[0] = 1;
		FOR(i, 1, SZ(f))
			f[i] = nf[i - 1] / i;
		ans[j] = n < SZ(f) ? f[n] : 0;
	}
	RFOR(i, SZ(ans), 1)
		ans[i] -= ans[i - 1];
	FOR(i, 0, n)
		cout << ans[i] << "\n";
	cerr << (db)clock() / CLOCKS_PER_SEC << endl;
	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5052kb

input:

1

output:

1.000000

result:

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

Test #2:

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

input:

2

output:

0.000000
1.000000

result:

ok 2 numbers

Test #3:

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

input:

3

output:

0.000000
0.333333
0.666667

result:

ok 3 numbers

Test #4:

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

input:

4

output:

0.000000
0.000000
0.666667
0.333333

result:

ok 4 numbers

Test #5:

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

input:

5

output:

0.000000
0.000000
0.333333
0.533333
0.133333

result:

ok 5 numbers

Test #6:

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

input:

6

output:

0.000000
0.000000
0.111111
0.555556
0.288889
0.044444

result:

ok 6 numbers

Test #7:

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

input:

7

output:

0.000000
0.000000
0.015873
0.444444
0.406349
0.120635
0.012698

result:

ok 7 numbers

Test #8:

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

input:

8

output:

0.000000
0.000000
0.000000
0.281746
0.466667
0.207143
0.041270
0.003175

result:

ok 8 numbers

Test #9:

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

input:

9

output:

0.000000
0.000000
0.000000
0.151675
0.465079
0.287831
0.082716
0.011993
0.000705

result:

ok 9 numbers

Test #10:

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

input:

10

output:

0.000000
0.000000
0.000000
0.069841
0.415573
0.352063
0.132011
0.027337
0.003034
0.000141

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 207ms
memory: 7944kb

input:

30000

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000003
0.000302
0.005594
0.034717
0.100...

result:

ok 30000 numbers

Test #12:

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

input:

56

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000010
0.006603
0.090982
0.244535
0.281571
0.200935
0.106277
0.045502
0.016498
0.005193
0.001441
0.000356
0.000079
0.000016
0.000003
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0...

result:

ok 56 numbers

Test #13:

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

input:

154

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000016
0.003140
0.044962
0.158145
0.245459
0.231697
0.159269
0.088257
0.041768
0.017455
0.006573
0.002259
0.000715
0.000210
0.000057
0.000015
0.000003
0.000001
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.0...

result:

ok 154 numbers

Test #14:

score: 0
Accepted
time: 3ms
memory: 5088kb

input:

230

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000002
0.000813
0.019865
0.102260
0.208792
0.240880
0.193014
0.121207
0.064024
0.029660
0.012357
0.004704
0.001653
0.000540
0.000165
0.000047
0.000013
0.000003
0.000001
0.000000
0.000000
0.000000
0.000000
0....

result:

ok 230 numbers

Test #15:

score: 0
Accepted
time: 3ms
memory: 5092kb

input:

198

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000060
0.005376
0.055051
0.166466
0.241986
0.223073
0.152998
0.085628
0.041259
0.017667
0.006853
0.002439
0.000803
0.000246
0.000071
0.000019
0.000005
0.000001
0.000000
0.000000
0.000000
0.000000
0.000000
0....

result:

ok 198 numbers

Test #16:

score: 0
Accepted
time: 5ms
memory: 4948kb

input:

274

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000040
0.003704
0.042194
0.142380
0.227886
0.227785
0.167404
0.099656
0.050903
0.023093
0.009504
0.003596
0.001263
0.000414
0.000127
0.000037
0.000010
0.000003
0.000001
0.000000
0.000000
0.000000
0....

result:

ok 274 numbers

Test #17:

score: 0
Accepted
time: 8ms
memory: 5036kb

input:

657

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000039
0.002644
0.029852
0.110316
0.198733
0.223622
0.183674
0.121416
0.068655
0.034495
0.015774
0.006666
0.002631
0.000976
0.000342
0.000114
0.000036
0.000011
0.000003
0....

result:

ok 657 numbers

Test #18:

score: 0
Accepted
time: 7ms
memory: 5168kb

input:

628

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000090
0.004352
0.039687
0.127501
0.209180
0.220854
0.173479
0.110991
0.061197
0.030120
0.013529
0.005626
0.002187
0.000800
0.000277
0.000091
0.000028
0.000008
0.000002
0...

result:

ok 628 numbers

Test #19:

score: 0
Accepted
time: 13ms
memory: 5048kb

input:

1319

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000002
0.000366
0.008487
0.052867
0.139377
0.207396
0.209939
0.163148
0.105218
0.059195
0.029995
0.013974
0.006067
0.002477
0.000957
0.000352
0.000123
...

result:

ok 1319 numbers

Test #20:

score: 0
Accepted
time: 13ms
memory: 5212kb

input:

1453

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000076
0.003264
0.030362
0.104885
0.187673
0.215824
0.183580
0.126498
0.074873
0.039525
0.019066
0.008537
0.003586
0.001423
0.000537
0.000193
0....

result:

ok 1453 numbers

Test #21:

score: 0
Accepted
time: 10ms
memory: 5052kb

input:

1095

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000091
0.003833
0.034370
0.113874
0.195872
0.217535
0.179503
0.120408
0.069532
0.035851
0.016894
0.007387
0.003027
0.001171
0.000430
0.000150
0.000050
0....

result:

ok 1095 numbers

Test #22:

score: 0
Accepted
time: 104ms
memory: 6332kb

input:

15826

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000000
0.000044
0.001711
0.017234
0.069000
0.145474
0.196004
0.1928...

result:

ok 15826 numbers

Test #23:

score: 0
Accepted
time: 111ms
memory: 5992kb

input:

12332

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000040
0.001632
0.016961
0.068941
0.146221
0.197180
0.193626
0.151883...

result:

ok 12332 numbers

Test #24:

score: 0
Accepted
time: 60ms
memory: 5424kb

input:

7285

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000049
0.001959
0.019581
0.076265
0.155347
0.202072
0.192289
0.146731
0.095490
0.055219
...

result:

ok 7285 numbers

Test #25:

score: 0
Accepted
time: 54ms
memory: 5432kb

input:

7621

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000021
0.001151
0.014091
0.063148
0.141854
0.197634
0.197443
0.156049
0.104233
0.061493
...

result:

ok 7621 numbers

Test #26:

score: 0
Accepted
time: 190ms
memory: 7752kb

input:

27875

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000015
0.000814
0.010537
0.050877
0.1234...

result:

ok 27875 numbers

Test #27:

score: 0
Accepted
time: 195ms
memory: 7984kb

input:

29438

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000000
0.000000
0.000005
0.000394
0.006640
0.038533
0.1064...

result:

ok 29438 numbers

Test #28:

score: 0
Accepted
time: 194ms
memory: 8016kb

input:

29062

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000007
0.000471
0.007435
0.041266
0.11...

result:

ok 29062 numbers

Test #29:

score: 0
Accepted
time: 219ms
memory: 7860kb

input:

29415

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000005
0.000399
0.006686
0.038696
0.10...

result:

ok 29415 numbers

Test #30:

score: 0
Accepted
time: 193ms
memory: 7956kb

input:

29394

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
0.000000
0.000000
0.000005
0.000403
0.006729
0.038846
0.10...

result:

ok 29394 numbers

Test #31:

score: 0
Accepted
time: 210ms
memory: 7936kb

input:

29485

output:

0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
0.000000
-0.000000
-0.000000
0.000000
-0.000000
-0.000000
-0.000000
0.000000
0.000000
0.000000
0.000005
0.000386
0.006546
0.038202
0.10...

result:

ok 29485 numbers