QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235365 | #667. Randomized Binary Search Tree | ckiseki# | TL | 2014ms | 12316kb | C++20 | 2.9kb | 2023-11-02 18:08:25 | 2023-11-02 18:08:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#include <experimental/iterator>
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
using llf = double;
using C = complex<llf>;
const llf PI = acos(llf(-1));
template <int maxn>
struct FFT {
C roots[maxn];
FFT() {
for (int i = maxn >> 1; i; i >>= 1) {
for (int j = 0; j < i; ++j)
roots[i + j] = polar<llf>(1, PI * j / i);
}
}
void operator()(C F[], int n, bool inv = false) {
for (int i = 0, j = 0; i < n; ++i) {
if (i < j) swap(F[i], F[j]);
for (int k = n >> 1; (j ^= k) < k; k >>= 1);
}
for (int s = 1; s < n; s *= 2) {
for (int i = 0; i < n; i += s * 2) {
for (int j = 0; j < s; j++) {
C a = F[i + j], b = F[i + j + s] * roots[s + j];
F[i + j] = a + b;
F[i + j + s] = a - b;
}
}
}
if (inv) {
for (int i = 0; i < n; ++i)
F[i] /= n;
reverse(F + 1, F + n);
}
}
};
FFT<1 << 18> fft;
vector<llf> mul(vector<llf> a, vector<llf> b) {
int sz = 1;
while (sz < int(a.size() + b.size()))
sz *= 2;
vector<C> A(sz), B(sz);
for (size_t i = 0; i < a.size(); ++i)
A[i] = C{a[i], 0};
for (size_t i = 0; i < b.size(); ++i)
B[i] = C{b[i], 0};
fft(A.data(), sz);
fft(B.data(), sz);
for (int i = 0; i < sz; ++i)
A[i] *= B[i];
fft(A.data(), sz, true);
vector<llf> c(a.size() + b.size() - 1);
for (size_t i = 0; i < c.size(); ++i)
c[i] = real(A[i]);
//for (size_t i = 0; i < a.size(); i++)
// for (size_t j = 0; j < b.size(); j++)
// c[i + j] += a[i] * b[j];
return c;
}
vector<llf> integ(vector<llf> a) {
a.insert(a.begin(), 0);
for (size_t i = 1; i < a.size(); i++)
a[i] /= i;
return a;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cout.precision(20);
cout << fixed;
int n; cin >> n;
vector<llf> g = {1};
//auto last = g;
//last[0] = 1;
//last[1] = 0;
for (int it = 0; it < n; it++) {
//orange(all(g));
if (it * n > 1500000)
{
cout << "0\n";
continue;
}
auto gg = g;
g = integ(mul(g, g));
g[0] += 1;
if (g.size() > 30001)
g.resize(30001);
auto v = g;
if (it == 0)
{
gg[0] = 0;
}
for (int i = 0; i < gg.size(); ++i)
v[i] -= gg[i];
orange(all(g));
orange(all(v));
if (g.size() > n) cout << v[n] << '\n';
else cout << "0" << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7904kb
input:
1
output:
1.00000000000000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 6ms
memory: 7908kb
input:
2
output:
0 1.00000000000000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 6ms
memory: 7960kb
input:
3
output:
0 0.33333333333333331483 0.66666666666666651864
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 8072kb
input:
4
output:
0 0 0.66666666666666651864 0.33333333333333325932
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 6ms
memory: 7972kb
input:
5
output:
0 0 0.33333333333333325932 0.53333333333333321491 0.13333333333333319271
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 6ms
memory: 7992kb
input:
6
output:
0 0 0.11111111111111104943 0.55555555555555546920 0.28888888888888863971 0.04444444444444362041
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 5ms
memory: 8076kb
input:
7
output:
0 0 0.01587301587301587907 0.44444444444444430875 0.40634920634920607130 0.12063492063492009532 0.01269841269841132103
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 5ms
memory: 7928kb
input:
8
output:
0 0 0 0.28174603174603174427 0.46666666666666634100 0.20714285714285640694 0.04126984126984012402 0.00317460317460160901
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 2ms
memory: 8028kb
input:
9
output:
0 0 0 0.15167548500881830598 0.46507936507936487036 0.28783068783068721519 0.08271604938271459595 0.01199294532627714904 0.00070546737213172950
result:
ok 9 numbers
Test #10:
score: 0
Accepted
time: 5ms
memory: 8004kb
input:
10
output:
0 0 0 0.06984126984126982907 0.41557319223985883516 0.35206349206349135672 0.13201058201058069042 0.02733686067019225341 0.00303350970017357557 0.00014109347442248232
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 115ms
memory: 12160kb
input:
30000
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.00000000000000000006 -0.00000000000000000002 0.00000000000000000028 -0.00000000000000000015 0.00000000000000000010 -0.00000000000000000019 -0.00000000000000000042 0.00000000000000000018 0.00000000000000000003 -0.00000000000000000283 0.00000000000000000383 -0.0000000000...
result:
ok 30000 numbers
Test #12:
score: 0
Accepted
time: 145ms
memory: 12120kb
input:
56
output:
0 0 0 0 0 0.00000000000000074544 0.00001005571821283289 0.00660281182019347140 0.09098155849589592559 0.24453503605629878237 0.28157059909569087663 0.20093514823312619288 0.10627731601666212669 0.04550174512118621006 0.01649757726914657940 0.00519314100284951063 0.00144092730091971433 0.000356009333...
result:
ok 56 numbers
Test #13:
score: 0
Accepted
time: 451ms
memory: 12284kb
input:
154
output:
0 0 0 0 0 0 0 -0.00000000000000001153 0.00000000018833079306 0.00001554381777536930 0.00314015014659804617 0.04496213442041847169 0.15814480517356035993 0.24545941703695389746 0.23169695454014227476 0.15926864898430781459 0.08825692922788075379 0.04176811195940721699 0.01745540201613771103 0.0065726...
result:
ok 154 numbers
Test #14:
score: 0
Accepted
time: 687ms
memory: 12196kb
input:
230
output:
0 0 0 0 0 0 0 -0.00000000000000001086 0.00000000000000000429 0.00000000000898870630 0.00000187186104500406 0.00081328109335230051 0.01986507472047740336 0.10225960707652508030 0.20879205059257843757 0.24087962933304818414 0.19301444207805962261 0.12120704421524042260 0.06402399834513472499 0.0296596...
result:
ok 230 numbers
Test #15:
score: 0
Accepted
time: 569ms
memory: 12120kb
input:
198
output:
0 0 0 0 0 0 0 -0.00000000000000000891 0.00000000000000003265 0.00000000782279327731 0.00005994658367346873 0.00537617606439282601 0.05505072727456675891 0.16646608730183715119 0.24198555781627531514 0.22307257692923604386 0.15299807331616410710 0.08562756792318504395 0.04125937829673465007 0.0176668...
result:
ok 198 numbers
Test #16:
score: 0
Accepted
time: 815ms
memory: 12112kb
input:
274
output:
0 0 0 0 0 0 0 0 0.00000000000000000000 0.00000000000000013724 0.00000000716181010576 0.00003970879034426985 0.00370438802927092409 0.04219404352872770797 0.14237962694849146117 0.22788577520506531071 0.22778524370367408958 0.16740361760938071711 0.09965647550981171499 0.05090343442214673164 0.023092...
result:
ok 274 numbers
Test #17:
score: 0
Accepted
time: 2014ms
memory: 12316kb
input:
657
output:
0 0 0 0 0 0 0 0 0 0.00000000000000000105 -0.00000000000000000204 0.00000000000000000160 0.00000000000004648784 0.00000002490354022285 0.00003863339552175437 0.00264378216892168080 0.02985224566437543262 0.11031635690266190786 0.19873273889984197083 0.22362161331615404425 0.18367423410748973112 0.121...
result:
ok 657 numbers
Test #18:
score: 0
Accepted
time: 1944ms
memory: 12312kb
input:
628
output:
0 0 0 0 0 0 0 0 0 -0.00000000000000000031 -0.00000000000000000093 0.00000000000000000484 0.00000000000057377877 0.00000010400635212997 0.00008953114309647901 0.00435205902221951109 0.03968698151572227356 0.12750125498677694624 0.20917986150261258516 0.22085379353290507387 0.17347872215763826542 0.11...
result:
ok 628 numbers
Test #19:
score: -100
Time Limit Exceeded
input:
1319
output:
0 0 0 0 0 0 0 0 0 0 0.00000000000000000054 0.00000000000000000198 -0.00000000000000000133 0.00000000000000000047 0.00000000000000008689 0.00000000029874192925 0.00000193677363683414 0.00036564929418054587 0.00848715010040175348 0.05286654930088705018 0.13937652590210813930 0.20739619959207611366 0.2...