QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99346 | #6299. Binary String | Hunster | WA | 3ms | 5532kb | C++14 | 1.7kb | 2023-04-21 22:06:17 | 2023-04-21 22:06:18 |
Judging History
answer
#include <bits/stdc++.h>
char str[10000005];
int n, next[10000005];
int main() {
int data_count;
scanf("%d", &data_count);
for (int data = 1; data <= data_count; data++) {
scanf("%s", str);
n = std::strlen(str);
[&] {
int cnt0 = 0;
for (int i = 0; i < n; i++) cnt0 += str[i] == '0';
if (cnt0 <= n / 2) {
std::reverse(str, str + n);
for (int i = 0; i < n; i++) str[i] = str[i] == '0' ? '1' : '0';
}
}();
int ans = [&] {
int max = 0;
for (int i = 0, now = 0; i < 5 * n; i++) {
int p = i % n;
if (str[p] == '1') now++;
else now--;
if (now < 0) now = 0;
max = std::max(max, now);
}
return max;
}() - 1;
for (int i = 0, now = 0, tag = 0; i < 5 * n; i++) {
int p = i % n;
if (str[p] == '1') now++;
if (now && !tag) {
str[p] = '1';
now--;
tag = 1;
}
else {
str[p] = '0';
tag = 0;
}
}
for (int i = n - 1; i >= 0; i--) str[i + 1] = str[i];
next[1] = 0;
for (int i = 2, j = 0; i <= n; i++) {
while (j != 0 && str[j + 1] != str[i]) j = next[j];
if (str[j + 1] == str[i]) j++;
next[i] = j;
}
if (n % (n - next[n]) == 0) ans += n - next[n];
else ans += n;
printf("%d\n", ans);
}
return 0;
}
/*
3
1
001001
0001111
*/
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 5532kb
input:
3 1 001001 0001111
output:
0 3 9
result:
wrong answer 1st numbers differ - expected: '1', found: '0'