QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282419#3247. 挑战kilo_tobo_tarjen#AC ✓698ms16548kbC++201.6kb2023-12-11 23:16:112023-12-11 23:16:11

Judging History

This is the latest submission verdict.

  • [2023-12-11 23:16:11]
  • Judged
  • Verdict: AC
  • Time: 698ms
  • Memory: 16548kb
  • [2023-12-11 23:16:11]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const char el = '\n';
typedef long long ll;
typedef double ld;
int n;
vector<ll> p, q;
pair<ld, ld> prob(int p, int q) {
  int a, b, c;
  if (p <= q)
    a = p * (p + 1) / 2, b = p, c = p * (q + 1) - b - a;
  else
    c = (q - 1) * q / 2, b = q, a = p * (q + 1) - b - c;
  return {1.0 * a / (a + b + c), 1.0 * c / (a + b + c)};
}
const int maxn = 1e5 + 5;
ld solve1(int k);
ld solve3(int k) {
  static vector<ld> mem(maxn, -1);
  if (k == n) return 1;
  ld &res = mem[k];
  if (res > -0.5) return res;
  res = 0;
  for (int i = 1; i <= p[k] && k + i <= n; i++) {
    res = max(res, 1 - solve1(k + i));
  }
  return res;
}
ld solve2(int k) {
  static vector<ld> mem(maxn, -1);
  if (k == n) return 1;
  ld &res = mem[k];
  if (res > -0.5) return res;
  res = 0;
  for (int i = 1; i <= p[k] && k + i <= n; i++) {
    res = max(res, solve1(k + i));
  }
  return res;
}
ld solve1(int k) {
  static vector<ld> mem(maxn, -1);
  if (k == n) return 0;
  ld &res = mem[k];
  if (res > -0.5) return res;
  res = 0;
  for (int i = 1; i <= p[k] && k + i <= n; i++) {
    res = max(res, 1 - solve1(k + i));
    if (p[k] == i || k + i == n) continue;
    auto [x, y] = prob(p[k] - i, q[k] + q[k + i]);
    res = max(res, x * solve3(k + i) + (1 - x - y) * (1 - solve1(k + i)) +
                       y * (1 - solve2(k + i)));
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(15);
  cin >> n;
  p.resize(n), q.resize(n);
  for (auto &v : p) cin >> v;
  for (auto &v : q) cin >> v;
  cout << solve1(0) << el;
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5724kb

input:

1000
5 1 33 33 35 2 28 10 2 24 12 19 30 32 3 23 27 3 35 15 13 24 27 13 5 25 3 27 16 18 35 17 11 6 22 1 30 12 11 25 12 17 15 6 17 5 4 25 5 26 2 23 7 18 21 18 31 24 1 15 29 15 16 33 28 23 24 12 13 26 25 28 2 9 27 2 25 16 27 5 20 17 4 4 35 17 17 24 2 27 35 28 3 15 33 33 7 9 6 2 9 34 29 10 27 15 16 32 2...

output:

0.925142814479831

result:

ok found '0.9251428', expected '0.9251428', error '0.0000000'

Test #2:

score: 0
Accepted
time: 8ms
memory: 14972kb

input:

99998
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #3:

score: 0
Accepted
time: 698ms
memory: 16496kb

input:

100000
333 333 333 333 333 332 331 333 332 331 331 332 331 332 333 331 333 331 332 330 330 333 332 333 331 333 332 330 330 333 332 330 330 333 331 331 333 331 331 333 331 331 330 332 331 333 332 332 332 330 333 330 332 332 333 330 331 332 332 331 332 331 331 330 330 332 333 333 333 331 330 330 333 3...

output:

0.5

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 5708kb

input:

1000
13 28 2 41 9 33 40 44 13 23 39 40 18 20 11 13 32 22 22 9 11 29 43 4 20 31 2 13 19 23 35 3 9 25 36 22 9 6 15 12 41 41 44 15 30 28 19 10 39 19 32 10 39 31 3 13 27 33 31 16 2 1 20 42 17 8 16 21 13 26 16 29 20 21 10 2 12 44 36 30 25 27 38 42 27 36 34 26 9 19 1 40 41 21 11 33 15 23 10 31 24 31 33 4 ...

output:

0.877824750544605

result:

ok found '0.8778248', expected '0.8778248', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 5684kb

input:

1000
46 69 32 80 20 9 30 55 31 28 75 61 9 83 3 28 47 20 37 51 23 49 38 43 59 50 63 33 54 45 61 20 44 84 38 33 88 6 88 25 80 26 53 49 44 16 55 68 80 2 40 5 34 42 38 10 44 35 8 5 90 80 8 27 8 81 73 20 74 74 36 21 78 47 10 19 52 12 45 61 75 51 23 10 7 71 55 71 39 52 18 36 11 78 59 76 87 23 44 54 45 36 ...

output:

0.903007793854058

result:

ok found '0.9030078', expected '0.9030078', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 5656kb

input:

1000
11 2 14 11 26 36 36 18 27 36 32 9 30 6 10 8 10 24 18 7 13 14 32 6 1 37 8 16 18 23 8 30 2 4 17 37 39 32 28 27 30 14 5 24 30 30 35 12 20 33 30 2 6 31 38 10 3 36 17 11 36 30 7 20 19 30 25 39 39 35 17 7 7 12 35 1 24 25 38 10 31 24 38 3 38 18 12 36 38 18 20 33 17 4 18 24 4 27 37 12 17 16 6 23 17 17 ...

output:

0.896935554594116

result:

ok found '0.8969356', expected '0.8969356', error '0.0000000'

Test #7:

score: 0
Accepted
time: 127ms
memory: 16468kb

input:

100000
3 6 6 333 2 3 3 100 100 333 1 5 2 4 100 2 4 5 1 3 100 333 6 5 6 333 100 1 1 2 4 100 3 3 333 5 3 4 3 100 4 333 1 4 2 6 6 6 6 100 5 5 5 3 333 2 1 3 333 3 3 3 2 2 100 5 4 2 2 100 1 3 2 100 5 6 2 5 2 2 3 5 1 4 2 3 6 2 5 6 333 333 2 4 4 6 4 3 100 333 1 2 2 100 333 4 6 3 4 6 1 100 100 4 6 100 5 2 6...

output:

0.00934832052641643

result:

ok found '0.0093483', expected '0.0093483', error '0.0000000'

Test #8:

score: 0
Accepted
time: 142ms
memory: 16548kb

input:

100000
3 100 4 3 5 5 5 333 2 5 2 2 2 2 2 4 2 333 5 3 3 5 333 1 100 2 2 5 100 333 5 1 3 3 2 333 4 5 4 5 1 333 333 333 1 100 2 4 333 1 2 1 4 100 4 3 5 1 2 2 3 5 3 4 1 4 100 3 2 333 5 5 4 2 100 3 2 5 100 100 4 1 3 333 3 333 100 1 1 1 100 100 1 333 5 4 100 5 2 5 5 4 100 3 1 100 4 333 100 333 2 4 5 333 2...

output:

0.00616771657079926

result:

ok found '0.0061677', expected '0.0061677', error '0.0000000'

Test #9:

score: 0
Accepted
time: 116ms
memory: 16500kb

input:

100000
1 1 5 6 333 6 100 7 3 5 333 1 1 6 2 100 7 7 6 100 6 100 100 2 1 4 5 333 333 4 2 4 4 100 6 2 7 7 6 333 6 333 1 4 4 4 3 2 100 2 5 7 6 1 2 3 5 2 100 5 7 1 6 5 1 3 1 333 5 1 6 333 2 1 333 3 333 1 1 2 6 5 3 3 1 2 333 3 2 7 4 2 6 6 1 1 5 100 5 3 5 100 333 1 7 7 333 1 1 5 6 3 1 100 5 100 7 1 7 6 4 5...

output:

0.0133352716246821

result:

ok found '0.0133353', expected '0.0133353', error '0.0000000'

Test #10:

score: 0
Accepted
time: 78ms
memory: 16508kb

input:

100000
5 8 6 14 12 6 2 12 13 14 5 14 10 10 3 5 5 11 100 10 14 8 333 333 100 5 12 333 14 3 7 3 12 7 2 14 12 11 13 6 11 100 333 6 9 2 14 1 14 6 100 14 5 1 6 4 100 1 5 1 9 4 12 6 3 6 12 11 8 12 11 3 6 11 9 3 13 9 2 3 333 12 9 100 100 5 8 8 2 8 1 3 4 14 100 100 12 9 100 9 8 7 3 9 10 10 7 333 333 2 8 2 1...

output:

0.469875077077287

result:

ok found '0.4698751', expected '0.4698751', error '0.0000000'

Test #11:

score: 0
Accepted
time: 3ms
memory: 14964kb

input:

99999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'