QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#282419 | #3247. 挑战 | kilo_tobo_tarjen# | AC ✓ | 698ms | 16548kb | C++20 | 1.6kb | 2023-12-11 23:16:11 | 2023-12-11 23:16:11 |
Judging History
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'