QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498901 | #667. Randomized Binary Search Tree | mshcherba | AC ✓ | 333ms | 8160kb | C++20 | 3.1kb | 2024-07-30 21:16:46 | 2024-07-30 21:16:46 |
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> com;
const db PI = acos(-1.0);
const int LEN = 1 << 16;
com pw[LEN];
void initFFT()
{
db angle = 2 * PI / LEN;
FOR(i, 0, LEN)
pw[i] = {cos(i * angle), sin(i * angle)};
}
void fft(vector<com>& a, bool inv)
{
int lg = __builtin_ctz(SZ(a));
FOR(i, 0, SZ(a))
{
int k = 0;
FOR(j, 0, lg)
k |= ((i >> j) & 1) << (lg - j - 1);
if(i < k)
swap(a[i], a[k]);
}
int k = inv ? LEN - LEN / 4 : LEN / 4;
//int g = inv ? binpow(GEN, mod - 2) : GEN, k = binpow(g, LEN / 4);
for(int len = 1; len < SZ(a); len *= 4)
{
if (2 * len == SZ(a))
{
int diff = inv ? LEN - LEN / (2 * len) : LEN / (2 * len), pos = 0;
// int ml = binpow(g, LEN / (2 * len)), pw = 1;
FOR(j, 0, len)
{
com u = a[j];
com v = a[j + len] * pw[pos];
a[j] = u + v;
a[j + len] = u - v;
pos = (pos + diff) % LEN;
// pw = mult(pw, ml);
}
}
else
{
int diff = inv ? LEN - LEN / (4 * len) : LEN / (4 * len), pos = 0;
// int ml = binpow(g, LEN / (4 * len)), pw = 1;
FOR(j, 0, len)
{
int pos2 = (2 * pos) % LEN, pos3 = (3 * pos) % LEN;
// int pw2 = mult(pw, pw), pw3 = mult(pw2, pw);
for(int i = j; i < SZ(a); i += 4 * len)
{
com a0 = a[i];
com a1 = a[i + len] * pw[pos2];
com a2 = a[i + 2 * len] * pw[pos];
com a3 = a[i + 3 * len] * pw[pos3];
com a0p1 = a0 + a1, a2p3 = a2 + a3,
a0m1 = a0 - a1, a2m3 = pw[k] * (a2 - a3); // pw[k] *
a[i] = a0p1 + a2p3;
a[i + len] = a0m1 + a2m3;
a[i + 2 * len] = a0p1 - a2p3;
a[i + 3 * len] = a0m1 - a2m3;
}
pos = (pos + diff) % LEN;
//pw = mult(pw, ml);
}
}
}
if(inv)
{
// int m = binpow(SZ(a), mod - 2);
FOR(i, 0, SZ(a))
a[i] /= SZ(a);
// a[i] = mult(a[i], m);
}
}
vector<db> mult(const vector<db>& a, const vector<db>& b)
{
vector<com> 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: 5156kb
input:
1
output:
1.000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5092kb
input:
2
output:
0.000000 1.000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 5140kb
input:
3
output:
0.000000 0.333333 0.666667
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 5228kb
input:
4
output:
0.000000 0.000000 0.666667 0.333333
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 5128kb
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: 5092kb
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: 5240kb
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: 5244kb
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: 5104kb
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: 5124kb
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: 333ms
memory: 8160kb
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: 5264kb
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...
result:
ok 56 numbers
Test #13:
score: 0
Accepted
time: 3ms
memory: 5260kb
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: 5332kb
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: 0ms
memory: 5332kb
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.0...
result:
ok 198 numbers
Test #16:
score: 0
Accepted
time: 2ms
memory: 5332kb
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: 5276kb
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 ...
result:
ok 657 numbers
Test #18:
score: 0
Accepted
time: 8ms
memory: 5408kb
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: 17ms
memory: 5376kb
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 0...
result:
ok 1319 numbers
Test #20:
score: 0
Accepted
time: 18ms
memory: 5252kb
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: 17ms
memory: 5412kb
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.0...
result:
ok 1095 numbers
Test #22:
score: 0
Accepted
time: 151ms
memory: 6340kb
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.19...
result:
ok 15826 numbers
Test #23:
score: 0
Accepted
time: 137ms
memory: 5980kb
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: 65ms
memory: 5680kb
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: 73ms
memory: 5708kb
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.0614...
result:
ok 7621 numbers
Test #26:
score: 0
Accepted
time: 294ms
memory: 8084kb
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.12342...
result:
ok 27875 numbers
Test #27:
score: 0
Accepted
time: 316ms
memory: 8160kb
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.10641...
result:
ok 29438 numbers
Test #28:
score: 0
Accepted
time: 333ms
memory: 7996kb
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.110...
result:
ok 29062 numbers
Test #29:
score: 0
Accepted
time: 331ms
memory: 8144kb
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.10666...
result:
ok 29415 numbers
Test #30:
score: 0
Accepted
time: 308ms
memory: 7948kb
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.106883...
result:
ok 29394 numbers
Test #31:
score: 0
Accepted
time: 305ms
memory: 8128kb
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.1059...
result:
ok 29485 numbers