QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557643#8668. 回文路径fairyqq2820 39ms10212kbC++141.7kb2024-09-11 10:40:322024-09-11 10:40:33

Judging History

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

  • [2024-09-11 10:40:33]
  • 评测
  • 测评结果:20
  • 用时:39ms
  • 内存:10212kb
  • [2024-09-11 10:40:32]
  • 提交

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], n - i - z[i] + 3);
        while (l < r) {
            int m = (l + r + 1) >> 1;
            gethsh1(i - z[i] - m, i - z[i]) == gethsh2(i + z[i] - 2, i + z[i] - 2 + m) ? l = m : r = m - 1;
        }
        // printf("%d %d %d\n", i, z[i], l);
        ans = max(ans, z[i] + l - 1);
    }
}

int main() {
    scanf("%d%s%s", &n, s[0] + 1, s[1] + 1);
    for (int i = pw[0] = 1; i <= N-5; ++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: 30
Accepted
time: 0ms
memory: 9408kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Wrong Answer
time: 2ms
memory: 8900kb

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

6

result:

wrong answer 1st lines differ - expected: '7', found: '6'

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 39ms
memory: 10068kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

score: 20
Accepted
time: 35ms
memory: 9976kb

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 35ms
memory: 10212kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 20
Accepted
time: 39ms
memory: 10064kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

9

result:

ok single line: '9'

Test #15:

score: 20
Accepted
time: 24ms
memory: 9920kb

input:

99999
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

99999

result:

ok single line: '99999'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%