QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#560512#667. Randomized Binary Search Treeucup-team1198#AC ✓198ms8512kbC++202.7kb2024-09-12 16:04:482024-09-12 16:04:48

Judging History

This is the latest submission verdict.

  • [2024-09-12 16:04:48]
  • Judged
  • Verdict: AC
  • Time: 198ms
  • Memory: 8512kb
  • [2024-09-12 16:04:48]
  • Submitted

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