QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#628993 | #8037. Gambler's Ruin | lonelywolf | WA | 1ms | 4032kb | C++20 | 1.7kb | 2024-10-10 23:51:59 | 2024-10-10 23:52:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
using db = double;
constexpr db eps = 1e-9;
int sgn(db x) {
if (x > eps) {
return 1;
} else if (x < -eps) {
return -1;
}
return 0;
}
int cmp(db x, db y) {
return sgn(x - y);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<db> p_(n + 1), c_(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p_[i] >> c_[i];
}
vector<int> ord(n + 1);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin() + 1, ord.end(), [&](int i, int j) {
return p_[i] > p_[j];
});
vector<db> p(1, -1);
vector<int> c(1);
int s1 = 0, s2 = 0;
for (int i = 1; i <= n; i++) {
if (cmp(p_[ord[i]], 0) == 0) {
s1 += c_[ord[i]];
} else if (cmp(p_[ord[i]], 1) == 0) {
s2 += c_[ord[i]];
} else if (cmp(p.back(), p_[ord[i]]) == 0) {
c[c.size() - 1] += c_[ord[i]];
} else {
p.push_back(p_[ord[i]]);
c.push_back(c_[ord[i]]);
}
}
vector<int> suf(n + 2);
for (int i = n; i >= 1; i--) {
suf[i] = suf[i + 1] + c[i];
}
n = p.size() - 1;
int sx = s2;
db ans = min(s1, s2);
for (int i = 1; i <= n; i++) {
assert(sgn(p[i]) == 1);
db x = 1.0 / p[i];
sx += c[i];
auto calc = [&](int m) {
assert(sgn(1 - p[m]) == 1);
db y = 1.0 / (1 - p[m]);
db sy = s1 + suf[m];
return 1.0 * sx + 1.0 * sy - max(x * sx, y * sy);
};
int l = i + 1, r = n;
while (r - l > 5) {
int lm = (2 * l + r) / 3, rm = (l + 2 * r) / 3;
if (calc(lm) < calc(rm)) {
l = lm;
} else {
r = rm;
}
}
for (int t = l; t <= r; t++) {
ans = max(ans, calc(t));
}
}
cout << fixed << setprecision(10) << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3972kb
input:
2 1 15 0 10
output:
10.0000000000
result:
ok found '10.0000000', expected '10.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
3 0.4 100 0.5 100 0.6 100
output:
33.3333333333
result:
ok found '33.3333333', expected '33.3333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1 0 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
2 1 0 1 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
1 0.5 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
3 0.4 100 0.6 100 0.6 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
3 0.2 100 0.2 100 0.8 100
output:
50.0000000000
result:
ok found '50.0000000', expected '50.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
2 0.999999 1000000 0.999998 2
output:
0.9999990000
result:
ok found '0.9999990', expected '0.9999990', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
2 0 100000 0.000001 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3748kb
input:
2 0 1000000000 0.000001 1
output:
0.0000000000
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '0.0000000', error = '1.0000000'