QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #756538 | #8037. Gambler's Ruin | Symmetree | WA | 2ms | 14184kb | C++17 | 1.7kb | 2024-11-16 20:51:07 | 2024-11-16 20:51:07 |
Judging History
answer
#include<bits/stdc++.h>
const int N = 1e6+5;
const double eps = 1e-10;
using i64 = long long;
std::pair<double, int> p[N];
i64 pre[N], suf[N];
double f[22][N];
int n, m, mxp[N], t[N];
#define fi first
#define se second
signed main() {
scanf("%d", &m);
i64 sum0 = 0, sum1 = 0;
for(int i = 1; i <= m; ++i) {
double x; int y;
scanf("%lf%d", &x, &y);
if(fabs(x) < eps) sum0 += y;
else if(fabs(1 - x) < eps) sum1 += y;
else p[++n] = {x, y};
}
// sx + sy - max(sx * x, sy * y)
// x = 1 / p[i], y = 1 / (1 - p[i])
//
std::sort(p + 1, p + n + 1);
pre[0] = p[0].se = sum0, p[0].fi = 0;
suf[n + 1] = p[n + 1].se = sum1, p[n + 1].fi = 1.0;
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + p[i].se;
for(int i = n; i; --i) suf[i] = suf[i + 1] + p[i].se;
for(int i = 0; i <= n; ++i) f[0][i] = 1.0 * pre[i] - 1.0 * pre[i] / (1 - p[i].fi);
for(int k = 1; k < 21; ++k)
for(int i = 1; i + (1 << k) - 1 <= n; ++i)
f[k][i] = std::max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]);
for(int i = 2; i <= n; ++i) t[i] = t[i >> 1] + 1;
double ans = -1e18;
for(int i = 1; i <= n + 1; ++i) {
int pos, l = 0, r = i - 1;
double bd = 1.0 * suf[i] / p[i].fi;
ans = std::max(ans, 1.0 * suf[i] - bd);
//if(i == 1) continue;
while(l < r) {
int mid = (l + r) >> 1;
if(1.0 * pre[mid] / (1.0 - p[mid].fi) >= bd) r = mid;
else l = mid + 1;
}
if(1.0 * pre[r] / (1.0 - p[r].fi) >= bd) {
int k = t[i - r];
ans = std::max(ans, 1.0 * suf[i] + std::max(f[k][r], f[k][i - (1 << k)]));
if(r > 1) ans = std::max(ans, 1.0 * suf[i] + 1.0 * pre[r] - bd);
}
else
ans = std::max(ans, 1.0 * suf[i] + 1.0 * pre[i - 1] - bd);
}
printf("%.10lf\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12068kb
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: 14184kb
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: 1ms
memory: 12072kb
input:
1 0 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 12072kb
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: 1ms
memory: 12136kb
input:
1 0.5 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 14096kb
input:
3 0.4 100 0.6 100 0.6 100
output:
33.3333333333
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '33.3333333', error = '33.3333333'