QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235375 | #667. Randomized Binary Search Tree | 8BQube# | AC ✓ | 150ms | 6436kb | C++20 | 2.7kb | 2023-11-02 18:23:32 | 2023-11-02 18:23:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())
const int C = 60;
using val_t = complex<double>;
template<int MAXN>
struct FFT {
const double PI = acos(-1);
val_t w[MAXN];
FFT() {
for (int i = 0; i < MAXN; ++i) {
double arg = 2 * PI * i / MAXN;
w[i] = val_t(cos(arg), sin(arg));
}
}
void bitrev(val_t *a, int n) {
int i = 0;
for (int j = 1; j < n - 1; ++j) {
for (int k = n >> 1; (i ^= k) < k; k >>= 1);
if (j < i) swap(a[i], a[j]);
}
}
void operator()(val_t *a, int n, bool inv = false) {
bitrev(a, n);
for (int L = 2; L <= n; L <<= 1) {
int dx = MAXN / L, dl = L >> 1;
for (int i = 0; i < n; i += L) {
for (int j = i, x = 0; j < i + dl; ++j, x += dx) {
val_t tmp = a[j + dl] * w[x];
a[j + dl] = a[j] - tmp;
a[j] += tmp;
}
}
}
if (inv) {
reverse(a + 1, a + n);
for (int i = 0; i < n; ++i) a[i] /= n;
}
}
};
const int N = 1 << 16;
#define fi(s, n) for (int i = (int)(s); i < (int)(n); ++i)
template<int MAXN>
struct Poly : vector<val_t> {
using vector<val_t>::vector;
static FFT<MAXN> fft;
int n() const { return (int)size(); }
Poly(const Poly &p, int m): vector<val_t>(m) {
copy_n(p.data(), min(p.n(), m), data());
}
Poly &isz(int m) { return resize(m), *this; }
Poly Mul(const Poly &rhs) const {
int m = 1;
while (m < n() + rhs.n() - 1) m <<= 1;
Poly X(*this, m), Y(rhs, m);
fft(X.data(), m), fft(Y.data(), m);
fi(0, m) X[i] = X[i] * Y[i];
fft(X.data(), m, true);
return X.isz(n() + rhs.n() - 1);
}
};
#undef fi
using Poly_t = Poly<N>;
template<> decltype(Poly_t::fft) Poly_t::fft = {};
FFT<N> fft;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
vector<val_t> dp(N);
dp[0] = 1;
cout << fixed << setprecision(8);
double last = 0;
for (int i = 1; i <= n && i < C; ++i) {
fft(dp.data(), N);
for (int j = 0; j < N; ++j)
dp[j] *= dp[j];
fft(dp.data(), N, true);
for (int j = n + 1; j < N; ++j)
dp[j] = 0;
for (int j = n; j >= 1; --j) {
dp[j] = val_t(dp[j - 1].real() / (double)j, 0);
}
dp[0] = 1;
cout << (dp[n].real() - last) << "\n";
last = dp[n].real();
}
for (int i = C; i <= n; ++i)
cout << (double)0 << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 6360kb
input:
1
output:
1.00000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 8ms
memory: 6412kb
input:
2
output:
0.00000000 1.00000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 11ms
memory: 6364kb
input:
3
output:
0.00000000 0.33333333 0.66666667
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 9ms
memory: 6360kb
input:
4
output:
0.00000000 0.00000000 0.66666667 0.33333333
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 16ms
memory: 6436kb
input:
5
output:
0.00000000 0.00000000 0.33333333 0.53333333 0.13333333
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 18ms
memory: 6300kb
input:
6
output:
0.00000000 0.00000000 0.11111111 0.55555556 0.28888889 0.04444444
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 21ms
memory: 6360kb
input:
7
output:
0.00000000 0.00000000 0.01587302 0.44444444 0.40634921 0.12063492 0.01269841
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 23ms
memory: 6388kb
input:
8
output:
0.00000000 0.00000000 0.00000000 0.28174603 0.46666667 0.20714286 0.04126984 0.00317460
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 25ms
memory: 6364kb
input:
9
output:
0.00000000 0.00000000 0.00000000 0.15167549 0.46507937 0.28783069 0.08271605 0.01199295 0.00070547
result:
ok 9 numbers
Test #10:
score: 0
Accepted
time: 23ms
memory: 6372kb
input:
10
output:
0.00000000 0.00000000 0.00000000 0.06984127 0.41557319 0.35206349 0.13201058 0.02733686 0.00303351 0.00014109
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 150ms
memory: 6320kb
input:
30000
output:
0.00000000 -0.00000000 -0.00000000 -0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.000000...
result:
ok 30000 numbers
Test #12:
score: 0
Accepted
time: 130ms
memory: 6372kb
input:
56
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00001006 0.00660281 0.09098156 0.24453504 0.28157060 0.20093515 0.10627732 0.04550175 0.01649758 0.00519314 0.00144093 0.00035601 0.00007890 0.00001577 0.00000286 0.00000047 0.00000007 0.00000001 0.00000000 0.00000000 0.00000000 0.0...
result:
ok 56 numbers
Test #13:
score: 0
Accepted
time: 139ms
memory: 6360kb
input:
154
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00001554 0.00314015 0.04496213 0.15814481 0.24545942 0.23169695 0.15926865 0.08825693 0.04176811 0.01745540 0.00657267 0.00225872 0.00071467 0.00020954 0.00005721 0.00001460 0.00000350 0.00000079 0.0...
result:
ok 154 numbers
Test #14:
score: 0
Accepted
time: 139ms
memory: 6364kb
input:
230
output:
0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000187 0.00081328 0.01986507 0.10225961 0.20879205 0.24087963 0.19301444 0.12120704 0.06402400 0.02965968 0.01235717 0.00470367 0.00165287 0.00054013 0.00016504 0.00004735 0.00001280 0....
result:
ok 230 numbers
Test #15:
score: 0
Accepted
time: 138ms
memory: 6408kb
input:
198
output:
0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000001 0.00005995 0.00537618 0.05505073 0.16646609 0.24198556 0.22307258 0.15299807 0.08562757 0.04125938 0.01766681 0.00685348 0.00243882 0.00080290 0.00024606 0.00007054 0.00001898 0.00000481 0.0...
result:
ok 198 numbers
Test #16:
score: 0
Accepted
time: 139ms
memory: 6408kb
input:
274
output:
0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000001 0.00003971 0.00370439 0.04219404 0.14237963 0.22788578 0.22778524 0.16740362 0.09965648 0.05090343 0.02309276 0.00950357 0.00359628 0.00126281 0.00041416 0.00012749 0.00003698 0....
result:
ok 274 numbers
Test #17:
score: 0
Accepted
time: 140ms
memory: 6320kb
input:
657
output:
0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000002 0.00003863 0.00264378 0.02985225 0.11031636 0.19873274 0.22362161 0.18367423 0.12141609 0.06865469 0.03449497 0.01577371 0.00666633 0.00263061...
result:
ok 657 numbers
Test #18:
score: 0
Accepted
time: 135ms
memory: 6364kb
input:
628
output:
0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000010 0.00008953 0.00435206 0.03968698 0.12750125 0.20917986 0.22085379 0.17347872 0.11099083 0.06119690 0.03011972 0.01352939 0.00562629 0.00218695...
result:
ok 628 numbers
Test #19:
score: 0
Accepted
time: 140ms
memory: 6388kb
input:
1319
output:
0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000194 0.00036565 0.00848715 0.05286655 0.13937653 0.20739620 0.20993877 0.16314815 0.10521768 0.05919518 0.02999516 ...
result:
ok 1319 numbers
Test #20:
score: 0
Accepted
time: 136ms
memory: 6296kb
input:
1453
output:
0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000015 0.00007624 0.00326397 0.03036206 0.10488488 0.18767301 0.21582450 0.18357961 0.12649831 0.07487279 0.03952523...
result:
ok 1453 numbers
Test #21:
score: 0
Accepted
time: 138ms
memory: 6360kb
input:
1095
output:
0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000017 0.00009062 0.00383265 0.03436978 0.11387389 0.19587237 0.21753544 0.17950258 0.12040819 0.06953194 0.03585063 0.01689363...
result:
ok 1095 numbers
Test #22:
score: 0
Accepted
time: 142ms
memory: 6408kb
input:
15826
output:
0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 -0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000015 0....
result:
ok 15826 numbers
Test #23:
score: 0
Accepted
time: 136ms
memory: 6224kb
input:
12332
output:
0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000012 0.00003975 0.0016...
result:
ok 12332 numbers
Test #24:
score: 0
Accepted
time: 138ms
memory: 6400kb
input:
7285
output:
0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000015 0.00004878 0.00195897 0.01958140 0.0762...
result:
ok 7285 numbers
Test #25:
score: 0
Accepted
time: 137ms
memory: 6312kb
input:
7621
output:
0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000004 0.00002123 0.00115080 0.01409084 0.0631...
result:
ok 7621 numbers
Test #26:
score: 0
Accepted
time: 143ms
memory: 6364kb
input:
27875
output:
0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 0....
result:
ok 27875 numbers
Test #27:
score: 0
Accepted
time: 147ms
memory: 6404kb
input:
29438
output:
0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0...
result:
ok 29438 numbers
Test #28:
score: 0
Accepted
time: 144ms
memory: 6316kb
input:
29062
output:
0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0...
result:
ok 29062 numbers
Test #29:
score: 0
Accepted
time: 142ms
memory: 6368kb
input:
29415
output:
0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0....
result:
ok 29415 numbers
Test #30:
score: 0
Accepted
time: 148ms
memory: 6316kb
input:
29394
output:
0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 -0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 -0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 ...
result:
ok 29394 numbers
Test #31:
score: 0
Accepted
time: 145ms
memory: 6364kb
input:
29485
output:
0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 0.00000000 -0.00000000 -0.00000000 0.00000000 0....
result:
ok 29485 numbers