QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234645 | #667. Randomized Binary Search Tree | PetroTarnavskyi# | AC ✓ | 219ms | 8016kb | C++17 | 2.2kb | 2023-11-01 20:14:16 | 2023-11-01 20:14:16 |
Judging History
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