QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#560512 | #667. Randomized Binary Search Tree | ucup-team1198# | AC ✓ | 198ms | 8512kb | C++20 | 2.7kb | 2024-09-12 16:04:48 | 2024-09-12 16:04:48 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const double PI = atan2l(0, -1);
using cd = complex<double>;
void fft(vector<cd>& a, bool inv = false) {
int n = a.size();
int k = 0;
while ((1 << k) < n) ++k;
static vector<int> rev;
static vector<cd> power = {0, 1};
rev.resize(n);
rev[0] = 0;
for (int i = 1; i < n; ++i) {
rev[i] = rev[i / 2] / 2 + ((i & 1) << (k - 1));
if (i < rev[i]) {
swap(a[i], a[rev[i]]);
}
}
for (int l = 1; l < n; l *= 2) {
if ((int)power.size() == l) {
power.resize(2 * l);
cd w = {cosl(PI / l), sinl(PI / l)};
for (int i = l; i < 2 * l; ++i) {
power[i] = power[i / 2];
if (i & 1) power[i] *= w;
}
}
for (int i = 0; i < n; i += 2 * l) {
for (int j = 0; j < l; ++j) {
cd x = a[i + j], y = a[i + j + l] * power[j + l];
a[i + j] = x + y;
a[i + j + l] = x - y;
}
}
}
if (inv) {
cd anti = {(double)1 / n, 0};
reverse(a.begin() + 1, a.end());
for (int i = 0; i < n; ++i) {
a[i] *= anti;
}
}
}
vector<double> operator*(vector<double> a, vector<double> b) {
int sz = a.size() + b.size() - 1;
int k = 0;
while ((1 << k) < sz) ++k;
vector<cd> ac(1 << k, {0, 0}), bc(1 << k, {0, 0});
for (int i = 0; i < (int)a.size(); ++i) {
ac[i] = {a[i], 0};
}
for (int i = 0; i < (int)b.size(); ++i) {
bc[i] = {b[i], 0};
}
fft(ac); fft(bc);
for (int i = 0; i < (1 << k); ++i) {
ac[i] *= bc[i];
}
fft(ac, true);
a.resize(sz);
for (int i = 0; i < sz; ++i) {
a[i] = ac[i].real();
}
return a;
}
const double EPS = 1e-6;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(20);
int n;
cin >> n;
int minh = 60;
vector<double> ans = {0};
vector<double> p = {1};
double lst = 0;
for (int h = 1; h <= n; ++h) {
p = p * p;
vector<double> res(p.size() + 1);
res[0] = 1;
for (int i = 1; i <= (int)p.size(); ++i) {
res[i] = p[i - 1] / i;
}
if (res.size() > n) {
res.resize(n + 1);
ans.push_back(res[n] - lst);
lst = res[n];
} else {
ans.push_back(0 - lst);
lst = 0;
}
p = res;
if (h >= minh && ans.back() < EPS && lst >= 0.5) {
break;
}
}
while ((int)ans.size() <= n) ans.push_back(0);
for (int i = 1; i <= n; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
1
output:
1.00000000000000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
2
output:
0.00000000000000000000 1.00000000000000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 4132kb
input:
3
output:
0.00000000000000000000 0.33333333333333331483 0.66666666666666651864
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 4188kb
input:
4
output:
0.00000000000000000000 0.00000000000000000000 0.66666666666666651864 0.33333333333333314830
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 4164kb
input:
5
output:
0.00000000000000000000 0.00000000000000000000 0.33333333333333325932 0.53333333333333321491 0.13333333333333352577
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 4156kb
input:
6
output:
0.00000000000000000000 0.00000000000000000000 0.11111111111111104943 0.55555555555555546920 0.28888888888888886175 0.04444444444444461961
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 4172kb
input:
7
output:
0.00000000000000000000 0.00000000000000000000 0.01587301587301587907 0.44444444444444430875 0.40634920634920618232 0.12063492063492020634 0.01269841269841220921
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 4244kb
input:
8
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.28174603174603174427 0.46666666666666622998 0.20714285714285696205 0.04126984126984090118 0.00317460317460260821
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
9
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.15167548500881830598 0.46507936507936487036 0.28783068783068743723 0.08271604938271492902 0.01199294532627759313 0.00070546737213328381
result:
ok 9 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 4244kb
input:
10
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.06984126984126982907 0.41557319223985866863 0.35206349206349174530 0.13201058201058124553 0.02733686067019325261 0.00303350970017601806 0.00014109347442636810
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 173ms
memory: 8412kb
input:
30000
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0...
result:
ok 30000 numbers
Test #12:
score: 0
Accepted
time: 1ms
memory: 4164kb
input:
56
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000076923 0.00001005571821279749 0.00660281182019346966 0.09098155849589606436 0.24453503605630036444 0.28157059909569703837 0.20093514823314095885 0.10627731601668588546 0...
result:
ok 56 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 4184kb
input:
154
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000001730 0.00000000018833078254 0.00001554381777536877 0.00314015014659807350 0.04496213442041974151 0.15814480517357104583 ...
result:
ok 154 numbers
Test #14:
score: 0
Accepted
time: 1ms
memory: 4180kb
input:
230
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000431 0.00000000000000000216 0.00000000000898869890 0.00000187186104499946 0.00081328109335228869 0.01986507472047849276 ...
result:
ok 230 numbers
Test #15:
score: 0
Accepted
time: 1ms
memory: 4252kb
input:
198
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000179 0.00000000000000002198 0.00000000782279325550 0.00005994658367347737 0.00537617606439293096 0.05505072727456990223 ...
result:
ok 198 numbers
Test #16:
score: 0
Accepted
time: 2ms
memory: 4328kb
input:
274
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000013083 0.00000000716181010588 0.00003970879034425702 0.00370438802927113616 0...
result:
ok 274 numbers
Test #17:
score: 0
Accepted
time: 5ms
memory: 4388kb
input:
657
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000045 -0.00000000000000000130 0.00000000000000000585 0.00000000000004647890...
result:
ok 657 numbers
Test #18:
score: 0
Accepted
time: 2ms
memory: 4300kb
input:
628
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000044 -0.00000000000000000115 0.00000000000000000186 0.00000000000057376854 ...
result:
ok 628 numbers
Test #19:
score: 0
Accepted
time: 9ms
memory: 4400kb
input:
1319
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000116 -0.00000000000000000046 -0.00000000000000000148...
result:
ok 1319 numbers
Test #20:
score: 0
Accepted
time: 10ms
memory: 4228kb
input:
1453
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000047 0.00000000000000000030 0.00000000000000000145 ...
result:
ok 1453 numbers
Test #21:
score: 0
Accepted
time: 9ms
memory: 4300kb
input:
1095
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000324 0.00000000000000000521 -0.00000000000000000104...
result:
ok 1095 numbers
Test #22:
score: 0
Accepted
time: 89ms
memory: 6008kb
input:
15826
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -...
result:
ok 15826 numbers
Test #23:
score: 0
Accepted
time: 87ms
memory: 5916kb
input:
12332
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -...
result:
ok 12332 numbers
Test #24:
score: 0
Accepted
time: 42ms
memory: 4764kb
input:
7285
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000018 ...
result:
ok 7285 numbers
Test #25:
score: 0
Accepted
time: 42ms
memory: 4744kb
input:
7621
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000024 ...
result:
ok 7621 numbers
Test #26:
score: 0
Accepted
time: 190ms
memory: 8512kb
input:
27875
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0...
result:
ok 27875 numbers
Test #27:
score: 0
Accepted
time: 160ms
memory: 8252kb
input:
29438
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0...
result:
ok 29438 numbers
Test #28:
score: 0
Accepted
time: 181ms
memory: 8380kb
input:
29062
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0...
result:
ok 29062 numbers
Test #29:
score: 0
Accepted
time: 198ms
memory: 8380kb
input:
29415
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0...
result:
ok 29415 numbers
Test #30:
score: 0
Accepted
time: 198ms
memory: 8364kb
input:
29394
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0...
result:
ok 29394 numbers
Test #31:
score: 0
Accepted
time: 194ms
memory: 8380kb
input:
29485
output:
0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0...
result:
ok 29485 numbers