QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557488 | #6218. 扭动的回文串 | Jerrywang | 100 ✓ | 46ms | 8060kb | C++14 | 2.1kb | 2024-09-11 09:55:40 | 2024-09-11 09:55:40 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'