QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#856278 | #6218. 扭动的回文串 | LaDeX | 100 ✓ | 51ms | 7856kb | C++17 | 1.9kb | 2025-01-13 20:22:27 | 2025-01-13 20:22:29 |
Judging History
answer
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 10;
const ull P = 1145141;
int n; char S[N], T[N];
ull hsh1[N], hsh2[N], hsh3[N], hsh4[N], base[N];
ull H2(int tp, int l, int r) {
if (tp == 1) return hsh1[r] - hsh1[l - 1] * base[r - l + 1];
return hsh2[r] - hsh2[l - 1] * base[r - l + 1];
}
ull H1(int tp, int l, int r) {
if (tp == 1) return hsh3[l] - hsh3[r + 1] * base[r - l + 1];
return hsh4[l] - hsh4[r + 1] * base[r - l + 1];
}
int Solve(int k1, int s, int k2, int t) {
int L = 0, R = min(s, n - t + 1);
while (L + 1 < R) {
int mid = (L + R) >> 1;
if (H1(k1, s - mid + 1, s) == H2(k2, t, t + mid - 1)) L = mid;
else R = mid;
}
if (H1(k1, s - R + 1, s) == H2(k2, t, t + R - 1)) return R;
return L;
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> (S + 1) >> (T + 1);
base[0] = 1;
for (int i = 1; i <= n; i ++) base[i] = base[i - 1] * P;
for (int i = 1; i <= n; i ++) hsh1[i] = hsh1[i - 1] * P + S[i];
for (int i = 1; i <= n; i ++) hsh2[i] = hsh2[i - 1] * P + T[i];
for (int i = n; i >= 1; i --) hsh3[i] = hsh3[i + 1] * P + S[i];
for (int i = n; i >= 1; i --) hsh4[i] = hsh4[i + 1] * P + T[i];
int Ans = 1;
for (int i = 1; i <= n; i ++) {
int even = Solve(1, i, 1, i + 1), odd = Solve(1, i, 1, i);
Ans = max(Ans, even * 2);
Ans = max(Ans, odd * 2 - 1);
Ans = max(Ans, Solve(1, i - even, 2, i + even) * 2 + even * 2);
Ans = max(Ans, Solve(1, i - odd, 2, i + odd - 1) * 2 + odd * 2 - 1);
}
for (int i = 1; i <= n; i ++) {
int even = Solve(2, i, 2, i + 1), odd = Solve(2, i, 2, i);
Ans = max(Ans, even * 2);
Ans = max(Ans, odd * 2 - 1);
Ans = max(Ans, Solve(1, i - even + 1, 2, i + even + 1) * 2 + even * 2);
Ans = max(Ans, Solve(1, i - odd + 1, 2, i + odd) * 2 + odd * 2 - 1);
}
for (int i = 1; i <= n; i ++)
Ans = max(Ans, Solve(1, i, 2, i) * 2);
cout << Ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 3584kb
input:
30 AABABAAAAABBBAAAAAABBAABAABABA AAAAAAABABBAAAAAABABAAAABAAAAB
output:
23
result:
ok single line: '23'
Test #2:
score: 10
Accepted
time: 1ms
memory: 3712kb
input:
200 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAAB ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAABBAAAAAAAABAAAAAAAAABAAAAAAAAAAAAAAAA...
output:
75
result:
ok single line: '75'
Test #3:
score: 10
Accepted
time: 0ms
memory: 5728kb
input:
200 AABAAAAAAAAAAAAAAAAAAAAABAAAAABAAABAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAABABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAAAAAAAABAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAABAAAAAAAAABBAAAAABAAAAAAAAAAAAAABAAAAABAAAAABBAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
117
result:
ok single line: '117'
Test #4:
score: 10
Accepted
time: 0ms
memory: 5864kb
input:
2000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAA...
output:
429
result:
ok single line: '429'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3840kb
input:
2000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAA...
output:
660
result:
ok single line: '660'
Test #6:
score: 10
Accepted
time: 48ms
memory: 7740kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
10486
result:
ok single line: '10486'
Test #7:
score: 10
Accepted
time: 50ms
memory: 7856kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
16715
result:
ok single line: '16715'
Test #8:
score: 10
Accepted
time: 47ms
memory: 7680kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
50035
result:
ok single line: '50035'
Test #9:
score: 10
Accepted
time: 51ms
memory: 7632kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
20929
result:
ok single line: '20929'
Test #10:
score: 10
Accepted
time: 48ms
memory: 7808kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
40448
result:
ok single line: '40448'