QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557643 | #8668. 回文路径 | fairyqq28 | 20 | 39ms | 10212kb | C++14 | 1.7kb | 2024-09-11 10:40:32 | 2024-09-11 10:40:33 |
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], 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%