QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414308 | #8668. 回文路径 | SunsetGlow95 | 100 ✓ | 77ms | 7924kb | C++20 | 4.5kb | 2024-05-18 20:41:11 | 2024-05-18 20:41:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MXN = 100005;
const int BSE = 26;
const char CBS = 'a';
struct HashVal {
static const int D1 = 998244353, D2 = 1e9 + 7;
int v1, v2;
HashVal(int _v1 = 0, int _v2 = 0) : v1(_v1), v2(_v2) {}
} pw[MXN], an[MXN], ar[MXN], bn[MXN], br[MXN];
HashVal operator+(HashVal lhs, HashVal rhs) {
return HashVal((lhs.v1 + rhs.v1) % HashVal::D1,
(lhs.v2 + rhs.v2) % HashVal::D2);
}
HashVal operator-(HashVal lhs, HashVal rhs) {
return HashVal((lhs.v1 - rhs.v1 + HashVal::D1) % HashVal::D1,
(lhs.v2 - rhs.v2 + HashVal::D2) % HashVal::D2);
}
HashVal operator*(HashVal lhs, HashVal rhs) {
return HashVal(lhs.v1 * 1LL * rhs.v1 % HashVal::D1,
lhs.v2 * 1LL * rhs.v2 % HashVal::D2);
}
bool operator==(HashVal lhs, HashVal rhs) {
return lhs.v1 == rhs.v1 && lhs.v2 == rhs.v2;
}
int N, ans;
char astr[MXN], bstr[MXN];
int main() {
scanf("%d %s %s", &N, astr + 1, bstr + 1);
pw[0] = HashVal(1, 1);
pw[1] = HashVal(BSE, BSE);
for (int i(1); i <= N; ++i) {
pw[i] = pw[i - 1] * pw[1];
an[i] = an[i - 1] + HashVal(astr[i] - CBS, astr[i] - CBS) * pw[i - 1];
bn[i] = bn[i - 1] + HashVal(bstr[i] - CBS, bstr[i] - CBS) * pw[i - 1];
}
for (int i(N); i >= 1; --i) {
ar[i] = ar[i + 1] + HashVal(astr[i] - CBS, astr[i] - CBS) * pw[N - i];
br[i] = br[i + 1] + HashVal(bstr[i] - CBS, bstr[i] - CBS) * pw[N - i];
}
//for (int i(1); i <= N; ++i) cout << pw[i].v1 << ' ' << pw[i].v2 << endl;
//for (int i(1); i <= N; ++i) cout << an[i].v1 << ' ' << an[i].v2 << endl;
//for (int i(1); i <= N; ++i) cout << ar[i].v1 << ' ' << ar[i].v2 << endl;
//for (int i(1); i <= N; ++i) cout << bn[i].v1 << ' ' << bn[i].v2 << endl;
//for (int i(1); i <= N; ++i) cout << br[i].v1 << ' ' << br[i].v2 << endl;
for (int i(1); i <= N; ++i) {
int l(1), r(min(i + 1, N - i + 2));
while (r - l > 1) {
int m((l + r) >> 1);
if ((bn[i] - bn[i - m]) * pw[N - i - m + 1] == (br[i] - br[i + m]) * pw[i - m])
l = m;
else
r = m;
}
int ln(l);
l = 0, r = min(i - ln + 1, N - i - ln + 1) + 1;
while (r - l > 1) {
int m((l + r) >> 1);
if ((an[i - ln + 1] - an[i - ln - m + 1]) * pw[N - i - ln - m + 1] ==
(br[i + ln] - br[i + ln + m]) * pw[i - ln - m + 1])
l = m;
else
r = m;
}
// cout << 'o' << i << ',' << ln << ',' << l << endl;
ans = max(ans, (ln + l) * 2 - 1);
}
for (int i(1); i <= N; ++i) {
int l(1), r(min(i + 1, N - i + 2));
while (r - l > 1) {
int m((l + r) >> 1);
if ((an[i] - an[i - m]) * pw[N - i - m + 1] == (ar[i] - ar[i + m]) * pw[i - m])
l = m;
else
r = m;
}
int ln(l);
l = 0, r = min(i - ln, N - i - ln + 2) + 1;
while (r - l > 1) {
int m((l + r) >> 1);
if ((an[i - ln] - an[i - ln - m]) * pw[N - i - ln - m + 2] ==
(br[i + ln - 1] - br[i + ln + m - 1]) * pw[i - ln - m])
l = m;
else
r = m;
}
// cout << 'o' << i << ',' << ln << ',' << l << endl;
ans = max(ans, (ln + l) * 2 - 1);
}
for (int i(1); i < N; ++i) {
int l(0), r(min(i + 1, N - i + 1));
while (r - l > 1) {
int m((l + r) >> 1);
if ((bn[i] - bn[i - m]) * pw[N - i - m] == (br[i + 1] - br[i + m + 1]) * pw[i - m])
l = m;
else
r = m;
}
int ln(l);
l = 0, r = min(i - ln + 1, N - i - ln) + 1;
while (r - l > 1) {
int m((l + r) >> 1);
if ((an[i - ln + 1] - an[i - ln - m + 1]) * pw[N - i - ln - m] ==
(br[i + ln + 1] - br[i + ln + m + 1]) * pw[i - ln - m + 1])
l = m;
else
r = m;
}
// cout << 'e' << i << ',' << ln << ',' << l << endl;
ans = max(ans, (ln + l) * 2);
}
for (int i(1); i < N; ++i) {
int l(0), r(min(i + 1, N - i + 1));
while (r - l > 1) {
int m((l + r) >> 1);
if ((an[i] - an[i - m]) * pw[N - i - m] == (ar[i + 1] - ar[i + m + 1]) * pw[i - m])
l = m;
else
r = m;
}
int ln(l);
l = 0, r = min(i - ln, N - i - ln + 1) + 1;
while (r - l > 1) {
int m((l + r) >> 1);
if ((an[i - ln] - an[i - ln - m]) * pw[N - i - ln - m + 1] ==
(br[i + ln] - br[i + ln + m]) * pw[i - ln - m])
l = m;
else
r = m;
}
// cout << 'e' << i << ',' << ln << ',' << l << endl;
ans = max(ans, (ln + l) * 2);
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 7520kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7736kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7588kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7520kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7880kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7672kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7524kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 0
Accepted
time: 2ms
memory: 7596kb
input:
1000 aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...
output:
36
result:
ok single line: '36'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7680kb
input:
1000 aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...
output:
50
result:
ok single line: '50'
Test #10:
score: 0
Accepted
time: 2ms
memory: 7712kb
input:
1000 aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...
output:
20
result:
ok single line: '20'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 66ms
memory: 7708kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 0
Accepted
time: 63ms
memory: 7664kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 0
Accepted
time: 62ms
memory: 7856kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 0
Accepted
time: 66ms
memory: 7840kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 0
Accepted
time: 68ms
memory: 7784kb
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok single line: '99999'
Subtask #3:
score: 50
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #16:
score: 50
Accepted
time: 62ms
memory: 7912kb
input:
100000 vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...
output:
10
result:
ok single line: '10'
Test #17:
score: 0
Accepted
time: 70ms
memory: 7768kb
input:
100000 fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...
output:
9
result:
ok single line: '9'
Test #18:
score: 0
Accepted
time: 76ms
memory: 7664kb
input:
100000 baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...
output:
40
result:
ok single line: '40'
Test #19:
score: 0
Accepted
time: 71ms
memory: 7916kb
input:
100000 babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...
output:
43
result:
ok single line: '43'
Test #20:
score: 0
Accepted
time: 77ms
memory: 7924kb
input:
100000 aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...
output:
75
result:
ok single line: '75'
Test #21:
score: 0
Accepted
time: 76ms
memory: 7860kb
input:
100000 aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...
output:
58
result:
ok single line: '58'
Test #22:
score: 0
Accepted
time: 77ms
memory: 7832kb
input:
100000 abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...
output:
67
result:
ok single line: '67'
Test #23:
score: 0
Accepted
time: 73ms
memory: 7844kb
input:
100000 bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...
output:
55
result:
ok single line: '55'
Test #24:
score: 0
Accepted
time: 72ms
memory: 7916kb
input:
100000 cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...
output:
25
result:
ok single line: '25'
Test #25:
score: 0
Accepted
time: 69ms
memory: 7920kb
input:
100000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...
output:
96421
result:
ok single line: '96421'
Test #26:
score: 0
Accepted
time: 1ms
memory: 7660kb
input:
5 pkusc pkukp
output:
6
result:
ok single line: '6'