QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#560504 | #667. Randomized Binary Search Tree | ucup-team1198# | WA | 9ms | 5972kb | C++20 | 2.7kb | 2024-09-12 16:02:03 | 2024-09-12 16:02:04 |
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 = 15;
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) {
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: 3860kb
input:
1
output:
1.00000000000000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4240kb
input:
2
output:
0.00000000000000000000 1.00000000000000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
3
output:
0.00000000000000000000 0.33333333333333331483 0.66666666666666651864
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
4
output:
0.00000000000000000000 0.00000000000000000000 0.66666666666666651864 0.33333333333333314830
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 4156kb
input:
5
output:
0.00000000000000000000 0.00000000000000000000 0.33333333333333325932 0.53333333333333321491 0.13333333333333352577
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 4168kb
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: 4152kb
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: 4136kb
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: 4168kb
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: 4172kb
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: -100
Wrong Answer
time: 9ms
memory: 5972kb
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:
wrong answer 30th numbers differ - expected: '0.00030', found: '0.00000', error = '0.00030'