QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557577 | #8668. 回文路径 | lyt_awa | 0 | 34ms | 9832kb | C++14 | 1.7kb | 2024-09-11 10:20:52 | 2024-09-11 10:20:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10, base = 42, P = 998244353;
int n, z[N], ans;
char s[2][N], t[2][N];
LL hsh[2][N], pw[N];
inline LL gethsh1(int l, int r) { return (hsh[0][r] - hsh[0][l - 1] * pw[r - l + 1] % P + P) % P; }
inline LL gethsh2(int l, int r) { return (hsh[1][l] - hsh[1][r + 1] * pw[r - l + 1] % P + P) % P; }
inline void solve(char *s1, char *s2) {
for (int j = 1; j <= n; ++j) hsh[0][j] = (hsh[0][j - 1] * base + s1[j]) % P;
for (int j = n; j >= 1; --j) hsh[1][j] = (hsh[1][j + 1] * base + s2[j]) % P;
// s1[n + 1] = s2[n + 1] = '\0';
// printf("%s\n%s\n", s1 + 1, s2 + 1);
for (int i = 1, mid, R = 0; i <= n; ++i) {
z[i] = i > R ? 1 : min(z[(mid << 1) - i], R - i + 1);
while (i - z[i] > 0 && i + z[i] <= n && s1[i - z[i]] == s1[i + z[i]]) ++z[i];
if (i + z[i] > R + 1) mid = i, R = i + z[i] - 1;
int l = 0, r = min(i - z[i] + 1, n - i - z[i] + 1);
while (l < r) {
int m = (l + r + 1) >> 1;
gethsh1(i - z[i] - m, i - z[i]) == gethsh2(i + z[i] - 1, i + z[i] - 1 + m) ? l = m : r = m - 1;
}
// printf("%d %d %d\n", i, z[i], l);
ans = max(ans, z[i] + l);
}
}
int main() {
scanf("%d%s%s", &n, s[0] + 1, s[1] + 1);
for (int i = pw[0] = 1; i <= n; ++i) (pw[i] = pw[i - 1] * base) %= P;
for (int j : {0, 1}) for (int i = 1; i <= n; ++i) t[j][i << 1] = s[j][i], t[j][(i << 1) - 1] = '|';
n = n << 1 | 1, t[0][n] = t[1][n] = '|';
solve(t[0], t[1]);
for (int i : {0, 1}) reverse(t[i] + 1, t[i] + n + 1);
solve(t[1], t[0]);
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5932kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
7
result:
wrong answer 1st lines differ - expected: '6', found: '7'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 34ms
memory: 9832kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
10
result:
wrong answer 1st lines differ - expected: '9', found: '10'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%