QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#817271 | #6218. 扭动的回文串 | SGColin | 100 ✓ | 144ms | 8360kb | C++20 | 2.6kb | 2024-12-16 21:18:15 | 2024-12-16 21:18:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
const int base = 31;
const int mod1 = 1000000007;
const int mod2 = 1000000009;
vector<pii> pw;
inline void init(int n) {
int pw1 = 1, pw2 = 1;
rep(i, 1, n) {
pw.eb(pw1, pw2);
pw1 = 1ll * pw1 * base % mod1;
pw2 = 1ll * pw2 * base % mod2;
}
}
struct HASH {
vector<pii> h;
HASH (string &str) {
int h1 = 0, h2 = 0;
for (auto c : str) {
int x = c - 'A' + 1;
h1 = (1ll * h1 * base + x) % mod1;
h2 = (1ll * h2 * base + x) % mod2;
h.eb(h1, h2);
}
}
inline pii getv(int l, int r) {
auto [h1, h2] = h[r];
if (l) {
auto [hl1, hl2] = h[l - 1];
auto [pw1, pw2] = pw[r - l + 1];
h1 = ((h1 - 1ll * hl1 * pw1) % mod1 + mod1) % mod1;
h2 = ((h2 - 1ll * hl2 * pw2) % mod2 + mod2) % mod2;
}
return {h1, h2};
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n; cin >> n; init(n);
string a, b; cin >> a >> b;
HASH A(a), B(b);
reverse(all(a));
reverse(all(b));
HASH RA(a), RB(b);
int ans = 0;
auto LCP = [&](HASH &x, HASH &y, int posx, int posy) {
int L = 0, R = min(n - posx, n - posy);
while (L < R) {
int mid = (L + R + 1) / 2;
x.getv(posx, posx + mid - 1) == y.getv(posy, posy + mid - 1) ? L = mid : R = mid - 1;
}
return L;
};
rep(i, 0, n - 1) { // centered at a character i
// center in A
int L = 1, R = min(n - i, i + 1);
while (L < R) {
int mid = (L + R + 1) / 2;
A.getv(i, i + mid - 1) == RA.getv(n - 1 - i, n - 2 + mid - i) ? L = mid : R = mid - 1;
}
ans = max(ans, L * 2 - 1 + LCP(RA, B, n - 1 - i + L, i + L - 1) * 2);
// center in B
L = 1, R = min(n - i, i + 1);
while (L < R) {
int mid = (L + R + 1) / 2;
B.getv(i, i + mid - 1) == RB.getv(n - 1 - i, n - 2 + mid - i) ? L = mid : R = mid - 1;
}
ans = max(ans, L * 2 - 1 + LCP(RA, B, n - 2 - i + L, i + L) * 2);
}
rep(i, 1, n) { // centered at a gap [i - 1, i]
// center in A
int L = 0, R = min(n - i, i);
while (L < R) {
int mid = (L + R + 1) / 2;
A.getv(i, i + mid - 1) == RA.getv(n - i, n - 1 + mid - i) ? L = mid : R = mid - 1;
}
ans = max(ans, L * 2 + LCP(RA, B, n - i + L, i + L - 1) * 2);
// center in B
L = 0, R = min(n - i, i);
while (L < R) {
int mid = (L + R + 1) / 2;
B.getv(i, i + mid - 1) == RB.getv(n - i, n - 1 + mid - i) ? L = mid : R = mid - 1;
}
ans = max(ans, L * 2 + LCP(RA, B, n - 1 - i + L, i + L) * 2);
}
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3748kb
input:
30 AABABAAAAABBBAAAAAABBAABAABABA AAAAAAABABBAAAAAABABAAAABAAAAB
output:
23
result:
ok single line: '23'
Test #2:
score: 10
Accepted
time: 1ms
memory: 3868kb
input:
200 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAAB ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAABBAAAAAAAABAAAAAAAAABAAAAAAAAAAAAAAAA...
output:
75
result:
ok single line: '75'
Test #3:
score: 10
Accepted
time: 0ms
memory: 3872kb
input:
200 AABAAAAAAAAAAAAAAAAAAAAABAAAAABAAABAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAABABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAAAAAAAABAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAABAAAAAAAAABBAAAAABAAAAAAAAAAAAAABAAAAABAAAAABBAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
117
result:
ok single line: '117'
Test #4:
score: 10
Accepted
time: 2ms
memory: 3860kb
input:
2000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAA...
output:
429
result:
ok single line: '429'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3932kb
input:
2000 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAA...
output:
660
result:
ok single line: '660'
Test #6:
score: 10
Accepted
time: 144ms
memory: 8360kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
10486
result:
ok single line: '10486'
Test #7:
score: 10
Accepted
time: 141ms
memory: 8128kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
16715
result:
ok single line: '16715'
Test #8:
score: 10
Accepted
time: 131ms
memory: 8128kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
50035
result:
ok single line: '50035'
Test #9:
score: 10
Accepted
time: 133ms
memory: 8220kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
20929
result:
ok single line: '20929'
Test #10:
score: 10
Accepted
time: 135ms
memory: 8196kb
input:
100000 ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
40448
result:
ok single line: '40448'