QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560504#667. Randomized Binary Search Treeucup-team1198#WA 9ms5972kbC++202.7kb2024-09-12 16:02:032024-09-12 16:02:04

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 16:02:04]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:5972kb
  • [2024-09-12 16:02:03]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'