QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#728023#5983. Pretty Good ProportionLarrix5 26093ms23728kbC++141.6kb2024-11-09 14:23:392024-11-09 14:24:00

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 14:24:00]
  • 评测
  • 测评结果:5
  • 用时:26093ms
  • 内存:23728kb
  • [2024-11-09 14:23:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr double eps = 1e-8;

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: 57ms
memory: 9944kb

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
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 26093ms
memory: 23728kb

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...

output:

Case #1: 6
Case #2: 0
Case #3: 0
Case #4: 2
Case #5: 0
Case #6: 0
Case #7: 0
Case #8: 0
Case #9: 0
Case #10: 0
Case #11: 0
Case #12: 0
Case #13: 0
Case #14: 0
Case #15: 0
Case #16: 4333
Case #17: 0
Case #18: 0
Case #19: 123
Case #20: 0
Case #21: 0
Case #22: 0
Case #23: 0
Case #24: 0
Case #25: 0
Case...

result:

wrong answer 30th lines differ - expected: 'Case #30: 681', found: 'Case #30: 676'