QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#850516#8668. 回文路径cooluo100 ✓29ms9724kbC++238.5kb2025-01-10 09:47:002025-01-10 09:47:05

Judging History

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

  • [2025-01-10 09:47:05]
  • 评测
  • 测评结果:100
  • 用时:29ms
  • 内存:9724kb
  • [2025-01-10 09:47:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define rsz resize
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define bit(k) (1 << (k))
#define Bit(k) (1ll << (k))
#define BIT(k) ((LL)1 << (k))
#define lowbit(x) ((x) & -(x))
#define bin(s, k) ((s) >> (k) & 1)
#define lg2(x) (31 - __builtin_clz(x))
#define LG2(x) (63 - __builtin_clzll(x))
#define popcnt(x) __builtin_popcount(x)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

// #define FILERR

#ifdef JYR
#ifdef FILERR
auto filerr = fopen("Test.err", "w");
#else
auto filerr = stderr;
#endif
#define errs(x) fputs(x "\n", filerr)
#define errm(x, ...) fprintf(filerr, x, ##__VA_ARGS__)
#else
#define errs(x) 0
#define errm(x, ...) 0
#endif

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_b < _a) _a = _b; }
template<typename T> T sq(T x) { return x * x; }

bool Mbe;

struct FastIO {
    char buf[1 << 20], *p1, *p2;
    char puf[1 << 20], *pf;

    FastIO() : p1(buf), p2(buf), pf(puf) {}
    ~FastIO() { fwrite(puf, 1, pf - puf, stdout); }

    char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin);
        return p1 == p2 ? EOF : *p1++;
    }

    bool blank(char c) { return c == ' ' || c == '\r' || c == '\n' || c == '\t'; }

    char rd() {
        char c = gc(); while (blank(c)) c = gc();
        return c;
    }

    template<typename T> T rd() {
        T x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        return f ? -x : x;
    }

    int rds(char *s) {
        char c = gc(), *S = s;
        while (blank(c)) c = gc();
        if (c == EOF) return *s = 0;
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }

    int rdl(char *s) {
        char c = gc(), *S = s;
        while (c == '\r' || c == '\n') c = gc();
        if (c == EOF) return *s = 0;
        while (c != '\r' && c != '\n' && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }

    void rd(char &c) { c = rd(); }

    template<typename T> void rd(T &x) {
        x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        if (f) x = -x;
    }

    template<typename T, typename... Ts>
    void rd(T& x, Ts&... xs) { rd(x), rd(xs...); }

    void pc(const char &c) {
        if (pf - puf == 1 << 20) fwrite(pf = puf, 1, 1 << 20, stdout);
        *pf++ = c;
    }

    void prt(char c) { pc(c); }

    template<typename T> void prt(T x) {
        static int st[41], tp = 0;
        if (x == 0) { pc('0'); return; }
        if (x < 0) x = -x, pc('-');
        while (x) st[++tp] = x % 10, x /= 10;
        while (tp) pc(st[tp--] + '0');
    }

    template<typename T> void prt(T *x) { while (*x) pc(*x++); }

    template<typename T, typename... Ts>
    void prt(T x, Ts... xs) { prt(x), prt(xs...); }

    void prts(const char *s, char c = '\n') {
        while (*s) pc(*s++);
        if (c) pc(c);
    }
} IO;

#define rd IO.rd
#define rds IO.rds
#define ri rd<int>()
#define rl rd<ll>()
#define prt IO.prt
#define edl IO.pc('\n')

// #define MC

#define N 100005
#define B 131
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

int n, ans;
char s[2][N];
ul hs[2][2][N], pw[N];

ul gths0(int i, int l, int r) { return hs[0][i][r] - hs[0][i][l - 1] * pw[r - l + 1]; }
ul gths1(int i, int l, int r) { return hs[1][i][l] - hs[1][i][r + 1] * pw[r - l + 1]; }

void mslv() {
    rd(n), rds(s[0] + 1), rds(s[1] + 1);
    pw[0] = 1;
    rep(i, 1, n) {
        pw[i] = pw[i - 1] * B;
        hs[0][0][i] = hs[0][0][i - 1] * B + s[0][i];
        hs[0][1][i] = hs[0][1][i - 1] * B + s[1][i];
    }
    per(i, n, 1) {
        hs[1][0][i] = hs[1][0][i + 1] * B + s[0][i];
        hs[1][1][i] = hs[1][1][i + 1] * B + s[1][i];
    }
    rep(i, 1, n) {
        int l = 0, r = min(i - 1, n - i), k = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(0, i - t, i) == gths1(0, i, i + t))
                k = t, l = t + 1;
            else r = t - 1;
        }
        // 0[i - k, i] == 0[i, i + k]
        // 0[i - k - K - 1, i - k - 1] == 1[i + k, i + k + K]
        // i - k - K - 1 >= 1 => K <= i - k - 2
        // i + k + K <= n => K <= n - i - k
        l = 0, r = min(i - k - 2, n - i - k);
        errm("[%d %d]\n", l, r);
        int K = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(0, i - k - t - 1, i - k - 1) == gths1(1, i + k, i + k + t))
                K = t, l = t + 1;
            else r = t - 1;
        }
        chkmx(ans, ((k + K + 1) << 1) + 1);
        errm("[#1] %d: %d %d | %d\n", i, k, K, ((k + K + 1) << 1) + 1);
    }
    req(i, 1, n) {
        int l = 0, r = min(i - 1, n - i - 1), k = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(0, i - t, i) == gths1(0, i + 1, i + t + 1))
                k = t, l = t + 1;
            else r = t - 1;
        }
        // 0[i - k, i] == 0[i + 1, i + k + 1]
        // 0[i - k - K - 1, i - k - 1] == 1[i + k + 1, i + k + K + 1]
        // i - k - K - 1 >= 1 => K <= i - k - 2
        // i + k + K + 1 <= n => K <= n - i - k - 1
        l = 0, r = min(i - k - 2, n - i - k - 1);
        int K = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(0, i - k - t - 1, i - k - 1) == gths1(1, i + k + 1, i + k + t + 1))
                K = t, l = t + 1;
            else r = t - 1;
        }
        chkmx(ans, (k + K + 2) << 1);
        errm("[#2] %d: %d %d | %d\n", i, k, K, (k + K + 2) << 1);
    }
    rep(i, 1, n) {
        int l = 0, r = min(i - 1, n - i), k = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(1, i - t, i) == gths1(1, i, i + t))
                k = t, l = t + 1;
            else r = t - 1;
        }
        // 1[i - k, i] == 1[i, i + k]
        // 0[i - k - K, i - k] == 1[i + k + 1, i + k + K + 1]
        // i - k - K >= 1 => K <= i - k - 1
        // i + k + K + 1 <= n => K <= n - i - k - 1
        l = 0, r = min(i - k - 1, n - i - k - 1);
        int K = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(0, i - k - t, i - k) == gths1(1, i + k + 1, i + k + t + 1))
                K = t, l = t + 1;
            else r = t - 1;
        }
        chkmx(ans, ((k + K + 1) << 1) + 1);
        errm("[#3] %d: %d %d | %d\n", i, k, K, ((k + K + 1) << 1) + 1);
    }
    rep(i, 2, n) {
        int l = 0, r = min(i - 2, n - i), k = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(1, i - t - 1, i - 1) == gths1(1, i, i + t))
                k = t, l = t + 1;
            else r = t - 1;
        }
        // 1[i - k - 1, i - 1] == 1[i, i + k]
        // 0[i - k - K - 1, i - k - 1] == 1[i + k + 1, i + k + K + 1]
        // i - k - K - 1 >= 1 => K <= i - k - 2
        // i + k + K + 1 <= n => K <= n - i - k - 1
        l = 0, r = min(i - k - 2, n - i - k - 1);
        int K = -1;
        while (l <= r) {
            int t = (l + r) >> 1;
            if (gths0(0, i - k - t - 1, i - k - 1) == gths1(1, i + k + 1, i + k + t + 1))
                K = t, l = t + 1;
            else r = t - 1;
        }
        chkmx(ans, (k + K + 2) << 1);
        errm("[#4] %d: %d %d | %d\n", i, k, K, (k + K + 2) << 1);
    }
    prt(ans);
}

void mprw() {}

bool Med;

int main() {
    #ifdef JYR
    errs("Running!");
    freopen("Test.in", "r", stdin);
    freopen("Test.out", "w", stdout);
    #endif
    mprw();
    #ifdef MC
    int _ = ri;
    while (_--) mslv();
    #else
    mslv();
    #endif
    errm("%.3lfMB %.0lfms\n", abs(&Med - &Mbe) / 1048576., clock() * 1000. / CLOCKS_PER_SEC);
    return 0;
}

详细

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 1ms
memory: 5636kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

6

result:

ok single line: '6'

Test #2:

score: 30
Accepted
time: 1ms
memory: 5640kb

input:

1000
wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...

output:

7

result:

ok single line: '7'

Test #3:

score: 30
Accepted
time: 1ms
memory: 5756kb

input:

1000
abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...

output:

28

result:

ok single line: '28'

Test #4:

score: 30
Accepted
time: 1ms
memory: 5732kb

input:

1000
ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...

output:

27

result:

ok single line: '27'

Test #5:

score: 30
Accepted
time: 0ms
memory: 5620kb

input:

1000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...

output:

987

result:

ok single line: '987'

Test #6:

score: 30
Accepted
time: 0ms
memory: 5704kb

input:

1000
aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...

output:

45

result:

ok single line: '45'

Test #7:

score: 30
Accepted
time: 0ms
memory: 5720kb

input:

1000
aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...

output:

45

result:

ok single line: '45'

Test #8:

score: 30
Accepted
time: 1ms
memory: 5728kb

input:

1000
aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...

output:

36

result:

ok single line: '36'

Test #9:

score: 30
Accepted
time: 1ms
memory: 5724kb

input:

1000
aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...

output:

50

result:

ok single line: '50'

Test #10:

score: 30
Accepted
time: 1ms
memory: 5724kb

input:

1000
aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...

output:

20

result:

ok single line: '20'

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 21ms
memory: 8428kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

9

result:

ok single line: '9'

Test #12:

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

input:

100000
fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...

output:

9

result:

ok single line: '9'

Test #13:

score: 20
Accepted
time: 20ms
memory: 7844kb

input:

99999
biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...

output:

11

result:

ok single line: '11'

Test #14:

score: 20
Accepted
time: 20ms
memory: 9424kb

input:

99999
chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...

output:

9

result:

ok single line: '9'

Test #15:

score: 20
Accepted
time: 19ms
memory: 8508kb

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: 24ms
memory: 7912kb

input:

100000
vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...

output:

10

result:

ok single line: '10'

Test #17:

score: 50
Accepted
time: 24ms
memory: 9280kb

input:

100000
fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...

output:

9

result:

ok single line: '9'

Test #18:

score: 50
Accepted
time: 28ms
memory: 7896kb

input:

100000
baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...

output:

40

result:

ok single line: '40'

Test #19:

score: 50
Accepted
time: 25ms
memory: 9164kb

input:

100000
babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...

output:

43

result:

ok single line: '43'

Test #20:

score: 50
Accepted
time: 26ms
memory: 9032kb

input:

100000
aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...

output:

75

result:

ok single line: '75'

Test #21:

score: 50
Accepted
time: 29ms
memory: 8476kb

input:

100000
aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...

output:

58

result:

ok single line: '58'

Test #22:

score: 50
Accepted
time: 25ms
memory: 7924kb

input:

100000
abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...

output:

67

result:

ok single line: '67'

Test #23:

score: 50
Accepted
time: 29ms
memory: 9724kb

input:

100000
bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...

output:

55

result:

ok single line: '55'

Test #24:

score: 50
Accepted
time: 23ms
memory: 8492kb

input:

100000
cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...

output:

25

result:

ok single line: '25'

Test #25:

score: 50
Accepted
time: 23ms
memory: 9104kb

input:

100000
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...

output:

96421

result:

ok single line: '96421'

Test #26:

score: 50
Accepted
time: 1ms
memory: 5672kb

input:

5
pkusc
pkukp

output:

6

result:

ok single line: '6'