QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414308#8668. 回文路径SunsetGlow95100 ✓77ms7924kbC++204.5kb2024-05-18 20:41:112024-05-18 20:41:12

Judging History

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

  • [2024-05-18 20:41:12]
  • 评测
  • 测评结果:100
  • 用时:77ms
  • 内存:7924kb
  • [2024-05-18 20:41:11]
  • 提交

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'