QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404025 | #6299. Binary String | alpha1022 | WA | 0ms | 3800kb | C++14 | 1.6kb | 2024-05-03 09:20:11 | 2024-05-03 09:20:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7;
char a[N + 5];
int n, s[N + 5], pos;
pair<int, int> stk[N + 5];
int top, res;
int b[N + 5], nxt[N + 5], ans;
void solve() {
scanf("%s", a + 1), n = strlen(a + 1); int c1 = 0;
for (int i = 1; i <= n; ++i) a[i] ^= '0', c1 += a[i];
if (c1 < n - c1) {
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) a[i] ^= 1;
}
pos = -1;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + (a[i] ? 1 : -1);
if (pos == -1 || s[i - 1] < s[pos - 1]) pos = i;
}
rotate(a + 1, a + pos, a + n + 1), res = 0, fill_n(b + 1, n, 0);
for (int l = 1, r; l <= n; l = r + 1) {
for (r = l; r < n && a[r + 1] == a[l]; ++r);
if (l == r) { if (a[l]) b[l] = 1; continue; }
if (a[l]) stk[++top] = {l, r - l + 1};
else {
int len = r - l + 1;
while (top && len > 1) {
auto &[l1, len1] = stk[top];
int c = min(len1 - 1, len - 1);
len1 -= c, len -= c, res = max(res, (r - len - l1 - len1 + 1) / 2);
if (len1 == 1) --top, b[l1] = 1;
}
}
}
for (int i = 1; i <= top; ++i) { auto &[l, len] = stk[i]; fill_n(b + l + 1, len, 1); }
for (int i = 1; i <= n; ++i) if (!b[i] && !b[i - 1]) b[i] = 1;
for (int i = 2, j = 0; i <= n; ++i) {
for (; j && b[j + 1] != b[i]; j = nxt[j]);
if (b[j + 1] == b[i]) ++j;
nxt[i] = j;
}
ans = res + n;
if (!(n % (n - nxt[n]))) ans -= nxt[n];
printf("%d\n", ans);
}
int T;
int main() {
//freopen("game.in", "r", stdin), freopen("game.out", "w", stdout);
for (scanf("%d", &T); T; --T) solve();
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3800kb
input:
3 1 001001 0001111
output:
1 6 9
result:
wrong answer 2nd numbers differ - expected: '3', found: '6'