QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235363 | #667. Randomized Binary Search Tree | ckiseki# | TL | 1147ms | 20976kb | C++20 | 2.9kb | 2023-11-02 18:07:18 | 2023-11-02 18:07:20 |
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 = long 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 > 2000000)
{
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 11796kb
input:
1
output:
1.00000000000000000000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 14ms
memory: 11712kb
input:
2
output:
0 1.00000000000000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 14ms
memory: 11816kb
input:
3
output:
0 0.33333333333333333334 0.66666666666666666663
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 14ms
memory: 11812kb
input:
4
output:
0 0 0.66666666666666666668 0.33333333333333333353
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 14ms
memory: 11828kb
input:
5
output:
0 0 0.33333333333333333332 0.53333333333333333347 0.13333333333333333354
result:
ok 5 numbers
Test #6:
score: 0
Accepted
time: 14ms
memory: 11768kb
input:
6
output:
0 0 0.11111111111111111113 0.55555555555555555567 0.28888888888888888907 0.04444444444444444468
result:
ok 6 numbers
Test #7:
score: 0
Accepted
time: 14ms
memory: 11908kb
input:
7
output:
0 0 0.01587301587301587302 0.44444444444444444447 0.40634920634920634945 0.12063492063492063525 0.01269841269841269867
result:
ok 7 numbers
Test #8:
score: 0
Accepted
time: 15ms
memory: 11860kb
input:
8
output:
0 0 0 0.28174603174603174606 0.46666666666666666686 0.20714285714285714322 0.04126984126984127018 0.00317460317460317487
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 15ms
memory: 11976kb
input:
9
output:
0 0 0 0.15167548500881834215 0.46507936507936507956 0.28783068783068783102 0.08271604938271604976 0.01199294532627866010 0.00070546737213403928
result:
ok 9 numbers
Test #10:
score: 0
Accepted
time: 15ms
memory: 12096kb
input:
10
output:
0 0 0 0.06984126984126984128 0.41557319223985890661 0.35206349206349206395 0.13201058201058201103 0.02733686067019400385 0.00303350970017636750 0.00014109347442680905
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 1147ms
memory: 20836kb
input:
30000
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.00000000000000000000 -0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 0.00000000000000000000 -0.00000000000000000000 -0.00000000000000000000 0.00000000000000000000 -0.00000000000000000000 -0.00000000000000000000 0.00000000000000000000 0.000000000000...
result:
ok 30000 numbers
Test #12:
score: 0
Accepted
time: 889ms
memory: 20976kb
input:
56
output:
0 0 0 0 0 0.00000000000000077985 0.00001005571821279373 0.00660281182019344961 0.09098155849589653121 0.24453503605630293722 0.28157059909570150187 0.20093514823314507790 0.10627731601669013358 0.04550174512122505925 0.01649757726919998200 0.00519314100292211711 0.00144092730101848260 0.000356009333...
result:
ok 56 numbers
Test #13:
score: -100
Time Limit Exceeded
input:
154