QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#336377#6299. Binary StringgoodierWA 86ms25824kbC++142.7kb2024-02-24 15:47:352024-02-24 15:47:35

Judging History

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

  • [2024-02-24 15:47:35]
  • 评测
  • 测评结果:WA
  • 用时:86ms
  • 内存:25824kb
  • [2024-02-24 15:47:35]
  • 提交

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'