QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#644690 | #3428. Spam Filter | crimsonsunset | AC ✓ | 27ms | 5560kb | C++20 | 1.1kb | 2024-10-16 15:07:36 | 2024-10-16 15:07:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
int k;
cin >> k;
string s;
cin >> s;
int n = s.size();
// cnt1 / cnt0 -> max
long double l = 0, r = n + 1;
int ans_i = 1, ans_len = k;
while (r - l > 0.0001) {
long double mid = (l + r) / 2;
vector<long double> pref(n + 1);
pref[0] = 0;
long double mn = 1e18;
int ind_mn = -1;
bool ok = false;
for (int i = 1; i <= n; ++i) {
long double now = 0;
if (s[i - 1] == '1')
now = 1;
else
now = -mid;
pref[i] = pref[i - 1] + now;
if (i >= k)
if (pref[i - k] < mn) {
mn = pref[i - k];
ind_mn = i - k;
}
if (pref[i] - mn >= 0) {
ok = true;
ans_i = ind_mn + 1;
ans_len = i - ans_i + 1;
}
}
if (ok)
l = mid;
else
r = mid;
}
cout << ans_i << ' ' << ans_len;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
5 1000100000
output:
1 5
result:
ok success rate = 2/5 (~0.400000)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
5 1111111111111101110111111110110111111110010101110000010000000000000100010101000000000101010000000110
output:
32 8
result:
ok success rate = 1/1 (~1.000000)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
20 1101101111110111101010011111001111010101110011001110110011101111111101111111111111111111111011111111
output:
70 22
result:
ok success rate = 1/1 (~1.000000)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
4 101110010100
output:
1 5
result:
ok success rate = 4/5 (~0.800000)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
4 101110010010
output:
1 5
result:
ok success rate = 4/5 (~0.800000)
Test #6:
score: 0
Accepted
time: 25ms
memory: 5372kb
input:
100 10000111111000101010100100000001001010001100110111100110110100100011111000001111001001010010001000111101101010101101010011101000001111000001001110011110000001001110100100000001000110100001101011001011001101000111101101011011111011101011011000110111010010101001111000101000011100010011000000100000...
output:
83971 100
result:
ok success rate = 17/25 (~0.680000)
Test #7:
score: 0
Accepted
time: 3ms
memory: 3752kb
input:
83 111011111011001100011001001111101111110111101110101111111111111111111111111111111111111111111100000000000000000000000000000000000100001000000000001101110011010110000000101101010101000110010110111111011111111011111111101110011101100111110100000100011110001000111011001101000101010000010010000000000...
output:
4144 88
result:
ok success rate = 83/88 (~0.943182)
Test #8:
score: 0
Accepted
time: 27ms
memory: 5556kb
input:
100 11110110111100000100110011001111111111100111111111111111100111111111111110110111001010111100111100001000001001000000000001111111111101111111111110000000000001100101100110000010010001000001100011000000000000001000000000001000000001100111111111101110101111111101011111110011010100011100001001100011...
output:
62033 129
result:
ok success rate = 125/129 (~0.968992)
Test #9:
score: 0
Accepted
time: 26ms
memory: 5224kb
input:
100 11111111111111101101111111111111111111111101100000000001000000000000001010001010001001100000000000000000000000000000000000000000000010000100000000010000000000111111111111111111111111001010111111111111111011111101011111000011111111010111000000000000000000010000000000000000000000100011001000010100...
output:
59424 103
result:
ok success rate = 100/103 (~0.970874)
Test #10:
score: 0
Accepted
time: 26ms
memory: 5560kb
input:
94 110000100010100000001101000000011000001000001000001110100000000000100010010110010101000000000000010000000000010100110111000000100010001010001011000110000000000000000000000000000000000000000011000010000110000101000000000000000010010000000000100001000100000100010110000100010011010000110011100000011...
output:
55082 98
result:
ok success rate = 47/49 (~0.959184)
Test #11:
score: 0
Accepted
time: 26ms
memory: 5380kb
input:
98 100100000000000100000011011111101111100011101111111000111011100010111101011101010111111111111110111111101111111111111111100000000001000000000010000000100000000000111111111111111110111101111111111110111111011101111110011110101011101011000010000000000000010000010010100000111111110111101111011111111...
output:
13883 98
result:
ok success rate = 47/49 (~0.959184)
Test #12:
score: 0
Accepted
time: 22ms
memory: 5532kb
input:
98 111111111111111000000101001111010000001001001100110000101000100000001000010111001111111111111110111111111111111101111111101111111111111111111111111111011111111111011111101110010011110011111111110111111000000100101000010011001000010101001101011100000011111111111111101101110001000001000000000000000...
output:
51563 113
result:
ok success rate = 107/113 (~0.946903)
Test #13:
score: 0
Accepted
time: 3ms
memory: 3712kb
input:
100 10011110010111111100111111110101110111111111110011111111111101111111111111101110111111111111111111111101111111111111111101111110000100101000000110010001000100000011100010111111101010111011111010111011110110000010100000000100000001000000001100010110110001111101111111111001111111000010110110011110...
output:
1838 104
result:
ok success rate = 97/104 (~0.932692)
Test #14:
score: 0
Accepted
time: 3ms
memory: 3752kb
input:
100 11111111111111101110111100000000000000000000000010000100000100000000000000000000000000000000001000000000001010001000101111011101111110100111101111100011011101111101111110111001111111110111011001000000000000000000000000000000100010100000100000110110100100001000001000000000000000000000000000000000...
output:
3254 117
result:
ok success rate = 8/9 (~0.888889)
Test #15:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
2 00000
output:
1 2
result:
ok success rate = 0/1 (~0.000000)
Test #16:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
2 1010101
output:
5 3
result:
ok success rate = 2/3 (~0.666667)
Test #17:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
20 000111000110000000111011100000001010001010010100111011101101001111111010111101000101001110010001100001011111111100110001011111001100001110101000011011000111011001011101011101100010010001000101100000100110010111110100001011100110000011000010001011111011111100101100100111111110001001100010111001010...
output:
489 27
result:
ok success rate = 7/9 (~0.777778)