QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#728040 | #5983. Pretty Good Proportion | Larrix | 5 | 71ms | 9956kb | C++14 | 1.6kb | 2024-11-09 14:25:47 | 2024-11-09 14:25:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr double eps = 1e-10;
int n, m;
char a[500005];
double p, l[500005], r[500005], pr[500005], lsh[500005];
#define lowbit(i) (i & -i)
double bit[500005];
void init(int n) { for (int i = 1; i <= n; i++) bit[i] = -1e18; }
void Upt(int k, double x) { for (int i = k; i <= m; i += lowbit(i)) bit[i] = max(bit[i], x); }
double Qry(int k) { double _(-1e18); for (int i = k; i; i -= lowbit(i)) _ = max(_, bit[i]); return _; }
int check(double mid) {
m = 0;
for (int i = n; i >= 0; i--) {
lsh[++m] = l[i] = pr[i] - i * mid, r[i] = pr[i] + i * mid;
}
sort(lsh + 1, lsh + m + 1);
m = unique(lsh + 1, lsh + m + 1) - lsh - 1;
init(m);
Upt(lower_bound(lsh + 1, lsh + m + 1, l[n]) - lsh, r[n]);
int rs(0);
for (int i = n - 1; i >= 0; i--) {
int id = lower_bound(lsh + 1, lsh + m + 1, l[i]) - lsh;
if (Qry(id) >= r[i]) rs = i + 1;
Upt(id, r[i]);
}
return rs;
}
int TT;
void solve() {
cin >> n >> p >> a + 1;
for (int i = 1; i <= n; i++) a[i] ^= 48, pr[i] = pr[i - 1] + a[i] - p;
double l = 0, r = max(1 - p, p);
while (l + eps < r) {
double mid((l + r) / 2);
if (check(mid)) r = mid;
else l = mid;
}
cout << "Case #" << ++TT << ": " << check(r)-1 << '\n';
}
signed main() {
#ifdef LARRIX
freopen("sample.in", "r", stdin);
freopen("sample.out", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T--) solve();
return 0;
}
/*
*/
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 71ms
memory: 9956kb
input:
100 10 0.827672 0010101011 4 0.932623 0100 1000 0.834002 011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...
output:
Case #1: 6 Case #2: 1 Case #3: 10 Case #4: 0 Case #5: 0 Case #6: 1 Case #7: 0 Case #8: 0 Case #9: 0 Case #10: 0 Case #11: 0 Case #12: 4 Case #13: 5 Case #14: 564 Case #15: 0 Case #16: 0 Case #17: 0 Case #18: 0 Case #19: 0 Case #20: 0 Case #21: 0 Case #22: 0 Case #23: 0 Case #24: 844 Case #25: 0 Case...
result:
ok 100 lines
Subtask #2:
score: 0
Time Limit Exceeded
Test #2:
score: 0
Time Limit Exceeded
input:
100 15 0.333333 000000000011000 10 0.418754 0101100001 2 0.499999 01 3 0.977951 001 2 0.249999 01 10 0.670229 0111011001 1000 0.500001 001101111110110010110000010010110001110010001101110111010011000010100011011101010110011011011010111110011100011000001000101011100011010100101101111110100101011010111...