QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557577#8668. 回文路径lyt_awa0 34ms9832kbC++141.7kb2024-09-11 10:20:522024-09-11 10:20:52

Judging History

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

  • [2024-09-11 10:20:52]
  • 评测
  • 测评结果:0
  • 用时:34ms
  • 内存:9832kb
  • [2024-09-11 10:20:52]
  • 提交

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%