QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#336377 | #6299. Binary String | goodier | WA | 86ms | 25824kb | C++14 | 2.7kb | 2024-02-24 15:47:35 | 2024-02-24 15:47:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int pos[3 * N], a[2 * N], T, ans, cnt[2], d[2 * N], Next[N], s[N], stk[2 * N], top;
char str[N];
int valid(int l, int r)
{
int s = 0;
for(int i = r; i >= l; i--)
{
if(a[i] == 1) s++;
else s--;
if(s < 0) return 0;
}
return 1;
}
int main()
{
//freopen("data.in", "r", stdin);
scanf("%d", &T);
while(T--)
{
ans = 0;
cnt[0] = cnt[1] = 0;
scanf("%s", str + 1);
int n = strlen(str + 1);
for(int i = 1; i <= 2 * n; i++) d[i] = 0;
for(int i = 0; i <= 3 * n; i++) pos[i] = -1;
for(int i = 1; i <= n; i++)
{
a[i] = str[i] - '0';
cnt[a[i]]++;
}
if(cnt[0] < cnt[1])
{
for(int i = 1; i <= n; i++) a[i] ^= 1;
reverse(a + 1, a + n + 1);
}
for(int i = 1; i <= n; i++) a[i + n] = a[i];
for(int i = 1, s = 0; i <= 2 * n; i++)
{
int x = a[i] == 1 ? 1 : -1;
s += x;
if(a[i] == 1 && i > n)
{
int len = i - pos[s + n];
d[i - len + 1]++, d[i + 1]--;
ans = max(ans, (i - stk[top--]) / 2);
}
else stk[++top] = i;
pos[s + n] = i;
}
for(int i = 1; i <= 2 * n; i++) d[i] += d[i - 1];
for(int i = 1; i <= n; i++) d[i] += d[i + n];
for(int i = 1; i <= n; i++) d[i + n] = d[i];
int flag = 0;
for(int st = 1; st <= n && !flag; st++)
{
if(!d[st])
{
flag = 1;
for(int i = st; i <= st + n - 1; i++)
{
if(!d[i])
{
s[i - st + 1] = 0;
}
else
{
int j = i;
while(j < st + n - 1 && d[j + 1]) j++;
for(int k = i, c = 0; k <= j; k++, c ^= 1)
{
s[k - st + 1] = c;
}
i = j;
}
}
}
}
if(!flag)
{
for(int i = 1, c = 0; i <= n; i++, c ^= 1)
{
s[i] = c;
}
}
for(int i = 2, j = 0; i <= n; i++)
{
while(j && s[j + 1] != s[i]) j = Next[j];
if(s[j + 1] == s[i]) j++;
Next[i] = j;
}
int t = (n % (n - Next[n])) ? n : n - Next[n];
ans += t;
printf("%d\n", ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3904kb
input:
3 1 001001 0001111
output:
1 3 9
result:
ok 3 number(s): "1 3 9"
Test #2:
score: -100
Wrong Answer
time: 86ms
memory: 25824kb
input:
262144 000000000000000000 100000000000000000 010000000000000000 110000000000000000 001000000000000000 101000000000000000 011000000000000000 111000000000000000 000100000000000000 100100000000000000 010100000000000000 110100000000000000 001100000000000000 101100000000000000 011100000000000000 11110000...
output:
1 18 18 19 18 18 19 20 18 18 18 19 19 20 20 21 18 18 18 19 18 18 19 20 19 19 20 21 20 21 21 22 18 18 18 19 18 18 19 20 18 18 18 19 19 20 20 21 19 19 19 19 20 21 21 22 20 21 21 22 21 22 22 23 18 18 18 19 18 18 19 20 18 18 18 19 19 20 20 21 18 18 18 19 18 18 19 20 19 19 20 21 20 21 21 22 19 19 19 19 1...
result:
wrong answer 12th numbers differ - expected: '20', found: '19'