QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557488#6218. 扭动的回文串Jerrywang100 ✓46ms8060kbC++142.1kb2024-09-11 09:55:402024-09-11 09:55:40

Judging History

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

  • [2024-09-11 09:55:40]
  • 评测
  • 测评结果:100
  • 用时:46ms
  • 内存:8060kb
  • [2024-09-11 09:55:40]
  • 提交

answer

// A
#include <cstdio>
#include <iostream>
#define ll unsigned long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
const int N=100010, B=131;
using namespace std;

int n, res; char a[2][N]; ll pw[N], h[2][2][N];
ll H0(ll h[2][N], int l, int r)
{
    return h[0][r]-h[0][l-1]*pw[r-l+1];
}
ll H1(ll h[2][N], int l, int r)
{
    return h[1][l]-h[1][r+1]*pw[r-l+1];
}

int main()
{
#ifdef Jerrywang
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%s%s", &n, &a[0][1], &a[1][1]);
    pw[0]=1; rep(i, 1, n) pw[i]=pw[i-1]*B;
    rep(k, 0, 1)
    {
        rep(i, 1, n) h[k][0][i]=h[k][0][i-1]*B+a[k][i];
        for(int i=n; i; i--) h[k][1][i]=h[k][1][i+1]*B+a[k][i];
    }
    rep(k, 0, 1) rep(i, 1, n)
    {
        int l=1, r=n, res1=0, res2=0;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(i+mid<=n && i-mid>=1 && H0(h[k], i, i+mid)==H1(h[k], i-mid, i))
                res1=mid, l=mid+1;
            else r=mid-1;
        }
        int l1=i-res1, r1=i+res1;
        l=1, r=n;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(k==0 && l1-mid>=1 && r1+mid-1<=n && H1(h[k], l1-mid, l1-1)==H0(h[k^1], r1, r1+mid-1)
            || k==1 && l1-mid+1>=1 && r1+mid<=n && H1(h[k^1], l1-mid+1, l1)==H0(h[k], r1+1, r1+mid))
                res2=mid, l=mid+1;
            else r=mid-1;
        }
        res=max(res, res1*2+1+res2*2);
        
        l=1, r=n, res1=0, res2=0;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(i+mid-1<=n && i-mid>=1 && H0(h[k], i, i+mid-1)==H1(h[k], i-mid, i-1))
                res1=mid, l=mid+1;
            else r=mid-1;
        }
        l1=i-res1, r1=i+res1-1;
        l=1, r=n;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(k==0 && l1-mid>=1 && r1+mid-1<=n && H1(h[k], l1-mid, l1-1)==H0(h[k^1], r1, r1+mid-1)
            || k==1 && l1-mid+1>=1 && r1+mid<=n && H1(h[k^1], l1-mid+1, l1)==H0(h[k], r1+1, r1+mid))
                res2=mid, l=mid+1;
            else r=mid-1;
        }
        res=max(res, res1*2+res2*2);
    }
    printf("%d", res);

    return 0;
}

详细


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 1ms
memory: 5780kb

input:

30
AABABAAAAABBBAAAAAABBAABAABABA
AAAAAAABABBAAAAAABABAAAABAAAAB

output:

23

result:

ok single line: '23'

Test #2:

score: 10
Accepted
time: 1ms
memory: 6028kb

input:

200
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAAB
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAABBAAAAAAAABAAAAAAAAABAAAAAAAAAAAAAAAA...

output:

75

result:

ok single line: '75'

Test #3:

score: 10
Accepted
time: 0ms
memory: 3860kb

input:

200
AABAAAAAAAAAAAAAAAAAAAAABAAAAABAAABAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAABABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAAAAAAAABAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAABAAAAAAAAABBAAAAABAAAAAAAAAAAAAABAAAAABAAAAABBAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

117

result:

ok single line: '117'

Test #4:

score: 10
Accepted
time: 0ms
memory: 4016kb

input:

2000
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAA...

output:

429

result:

ok single line: '429'

Test #5:

score: 10
Accepted
time: 1ms
memory: 6000kb

input:

2000
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAA...

output:

660

result:

ok single line: '660'

Test #6:

score: 10
Accepted
time: 40ms
memory: 8000kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

10486

result:

ok single line: '10486'

Test #7:

score: 10
Accepted
time: 45ms
memory: 8060kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

16715

result:

ok single line: '16715'

Test #8:

score: 10
Accepted
time: 45ms
memory: 8056kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

50035

result:

ok single line: '50035'

Test #9:

score: 10
Accepted
time: 42ms
memory: 7992kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

20929

result:

ok single line: '20929'

Test #10:

score: 10
Accepted
time: 46ms
memory: 8056kb

input:

100000
ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

40448

result:

ok single line: '40448'