QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#728005#5983. Pretty Good ProportionLarrix0 26206ms23840kbC++141.5kb2024-11-09 14:21:302024-11-09 14:21:31

Judging History

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

  • [2024-11-09 14:21:31]
  • 评测
  • 测评结果:0
  • 用时:26206ms
  • 内存:23840kb
  • [2024-11-09 14:21:30]
  • 提交

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;
}

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 << check(r) << '\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: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 57ms
memory: 9956kb

input:

100
10 0.827672
0010101011
4 0.932623
0100
1000 0.834002
011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...

output:

7
2
11
1
1
2
1
1
1
1
1
5
6
565
1
1
1
1
1
1
1
1
1
845
1
1
2
156
1
1
1
1
1
1
394
2
174
1
3
1
131
4
1
841
2
6
1
1
75
1
2
1
1
1
1
1
2
1
2
1
1
1
9
1
1
839
3
3
1
1
1
613
1
6
1
1
1
1
1
1
2
1
321
1
1
7
80
1
1
1
1
1
2
1
2
159
1
1
4
1

result:

wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 26206ms
memory: 23840kb

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:

7
1
1
3
1
1
1
1
1
1
1
1
1
1
1
4334
1
1
124
1
1
1
1
1
1
1
1
4
1
677
1
1
3
1
1
1
1
1
2
3
1
279
3
2
2
1
1
1
1
1
1
1
1
2
1
2
1
6
6
1
2
2
1
3
2
1
7
4
1
501
2
1
1
2
1
2
189
4
1
7
499839
1
1
6
1
1
1
499841
1
1
9
5
1
2
1
1
1
93
1
1

result:

wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'