QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288647#275. PalindromesMax_s_xaM100 ✓148ms23552kbC++146.1kb2023-12-23 10:06:282023-12-23 10:06:30

Judging History

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

  • [2023-12-23 10:06:30]
  • 评测
  • 测评结果:100
  • 用时:148ms
  • 内存:23552kb
  • [2023-12-23 10:06:28]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <cstring>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 3e5 + 10;

int n, m;
ll ans;
char s[MAXN];

int sa[MAXN], rk[MAXN], p[MAXN << 1], cnt[MAXN], ht[MAXN];
int lb[MAXN], rb[MAXN], st[MAXN], top;

int pl[MAXN], id[MAXN];

int tr[MAXN << 2];
inline void Pushup(int cur) {tr[cur] = max(tr[cur << 1], tr[cur << 1 | 1]);}
void Update(int cur, int l, int r, int x)
{
    if (l == r) tr[cur] = x;
    else
    {
        int mid = l + r >> 1;
        if (x <= mid) Update(cur << 1, l, mid, x);
        else Update(cur << 1 | 1, mid + 1, r, x);
        Pushup(cur);
    }
}
int Query(int cur, int l, int r, int x)
{
    if (x <= 0) return -1;
    if (r <= x) return tr[cur];
    int mid = l + r >> 1, res = Query(cur << 1, l, mid, x);
    if (x > mid) res = max(res, Query(cur << 1 | 1, mid + 1, r, x));
    return res;
}

int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(s + 1), n = strlen(s + 1);
    m = 127;
    for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
    for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; i++) sa[++cnt[rk[i] - 1]] = i;
    for (int w = 1; w <= n; w <<= 1)
    {
        int top = 0;
        for (int i = n - w + 1; i <= n; i++) p[++top] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > w) p[++top] = sa[i] - w;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++) cnt[rk[i]]++;
        for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = 1; i <= n; i++) sa[++cnt[rk[p[i]] - 1]] = p[i];
        memcpy(p, rk, sizeof(rk));
        m = 0;
        for (int i = 1; i <= n; i++)
            rk[sa[i]] = (p[sa[i]] == p[sa[i - 1]] && p[sa[i] + w] == p[sa[i - 1] + w] ? m : ++m);
        if (m == n) break;
    }
    for (int i = 1, j = 0; i <= n; i++)
    {
        if (rk[i] == 1) continue;
        if (j) j--;
        while (i + j <= n && sa[rk[i] - 1] + j <= n && s[i + j] == s[sa[rk[i] - 1] + j]) j++;
        ht[rk[i]] = j;
    }
    // lb[i] -> rk[i] leftbound
    st[top = 1] = 1;
    for (int i = 2; i <= n; i++)
    {
        while (top > 1 && ht[st[top]] >= ht[i]) top--;
        lb[i] = st[top], st[++top] = i;
    }
    st[top = 1] = n + 1;
    for (int i = n; i >= 2; i--)
    {
        while (top > 1 && ht[st[top]] >= ht[i]) top--;
        rb[i] = st[top] - 1, st[++top] = i;
    }
    // for (int i = 1; i <= n; i++) cout << lb[i] << " "; cout << "\n";
    // for (int i = 1; i <= n; i++) cout << rb[i] << " "; cout << "\n";

    for (int i = 1, l = 0, r = 0; i <= n; i++)
    {
        pl[i] = (i > r ? 0 : min(pl[l + r - i], r - i));
        while (i + pl[i] < n && i - pl[i] > 1 && s[i + pl[i] + 1] == s[i - pl[i] - 1]) pl[i]++;
        if (i + pl[i] > r) l = i - pl[i], r = i + pl[i];
        ans = max(ans, pl[i] * 2ll + 1);
    }
    // for (int i = 1; i <= n; i++) cout << pl[i] << " "; cout << "\n";
    for (int i = 1; i <= n; i++) id[i] = i;
    sort(id + 1, id + n + 1, [&](int x, int y) {return x - pl[x] < y - pl[y];});
    memset(tr, -1, sizeof(tr));
    for (int i = 1, j = 1; i <= n; i++)
    {
        if (rk[i] == 1 || ht[rk[i]] == 0) continue;
        while (j <= n && id[j] - pl[id[j]] <= i) Update(1, 1, n, id[j]), j++;
        int cur = Query(1, 1, n, i + (ht[rk[i]] - 1) / 2);
        if (cur >= i) ans = max(ans, (ll)(2 * cur - 2 * i + 1) * (rb[rk[i]] - lb[rk[i]] + 1));
    }

    for (int i = 1, l = 0, r = 0; i <= n; i++)
    {
        pl[i] = (i > r ? -1 : min(pl[l + r - i - 1], r - i - 1));
        while (i + pl[i] + 1 < n && i - pl[i] > 1 && s[i + pl[i] + 2] == s[i - pl[i] - 1]) pl[i]++;
        if (i + pl[i] + 1 > r) l = i - pl[i], r = i + pl[i] + 1;
        ans = max(ans, pl[i] * 2ll + 2);
    }
    for (int i = 1; i <= n; i++) id[i] = i;
    sort(id + 1, id + n + 1, [&](int x, int y) {return x - pl[x] < y - pl[y];});
    memset(tr, -1, sizeof(tr));
    for (int i = 1, j = 1; i <= n; i++)
    {
        if (rk[i] == 1 || ht[rk[i]] == 0) continue;
        while (j <= n && id[j] - pl[id[j]] <= i) Update(1, 1, n, id[j]), j++;
        int cur = Query(1, 1, n, i - 1 + ht[rk[i]] / 2);
        if (cur >= i) ans = max(ans, (ll)(2 * cur - 2 * i + 2) * (rb[rk[i]] - lb[rk[i]] + 1));
    }
    Write(ans, '\n');
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 0ms
memory: 21340kb

input:

abacaba

output:

7

result:

ok single line: '7'

Test #2:

score: 0
Accepted
time: 0ms
memory: 21424kb

input:

www

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 23552kb

input:

abacababa

output:

9

result:

ok single line: '9'

Test #4:

score: 0
Accepted
time: 4ms
memory: 19760kb

input:

r

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 22724kb

input:

xd

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 22144kb

input:

dd

output:

2

result:

ok single line: '2'

Test #7:

score: 0
Accepted
time: 4ms
memory: 22088kb

input:

opo

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 0ms
memory: 21444kb

input:

opoo

output:

3

result:

ok single line: '3'

Test #9:

score: 0
Accepted
time: 0ms
memory: 22340kb

input:

abacabadabacaba

output:

15

result:

ok single line: '15'

Test #10:

score: 0
Accepted
time: 0ms
memory: 21872kb

input:

xxxxxyxxxxyxxxxx

output:

24

result:

ok single line: '24'

Test #11:

score: 0
Accepted
time: 0ms
memory: 21520kb

input:

xxxyxxxyzzzabcdxxdcba

output:

10

result:

ok single line: '10'

Test #12:

score: 0
Accepted
time: 0ms
memory: 21932kb

input:

qpppppppwowpppppq

output:

24

result:

ok single line: '24'

Test #13:

score: 0
Accepted
time: 0ms
memory: 22424kb

input:

mqmwmemrmtymmmmmmmmqwertyeeeeeeeee

output:

25

result:

ok single line: '25'

Test #14:

score: 0
Accepted
time: 0ms
memory: 21784kb

input:

mqmwmmmmmemrmtymmmmmmmmqwertyeeeeeeeee

output:

28

result:

ok single line: '28'

Test #15:

score: 0
Accepted
time: 0ms
memory: 23020kb

input:

abcdefghijklmnopqrstuvwxyzz

output:

2

result:

ok single line: '2'

Test #16:

score: 0
Accepted
time: 0ms
memory: 22192kb

input:

abcdefghijklmnopqrstuvwxyz

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 0ms
memory: 21308kb

input:

apiodpdpdpdpdpgoodchallenge

output:

15

result:

ok single line: '15'

Test #18:

score: 0
Accepted
time: 0ms
memory: 22376kb

input:

pdpdpdpxdpdpdxdpdpdx

output:

18

result:

ok single line: '18'

Test #19:

score: 0
Accepted
time: 5ms
memory: 23032kb

input:

jejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejejeje

output:

1176

result:

ok single line: '1176'

Test #20:

score: 0
Accepted
time: 0ms
memory: 22752kb

input:

wzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzw

output:

1225

result:

ok single line: '1225'

Test #21:

score: 0
Accepted
time: 0ms
memory: 22508kb

input:

qsqsqsqsqsqsqianananananananananaygsgsgsgsgsgsgsgsgsgsgsgsgsgsgsgszikidnsnsnsnsnsnsnsnsnsnsnsnsn

output:

136

result:

ok single line: '136'

Test #22:

score: 0
Accepted
time: 2ms
memory: 23136kb

input:

hsoqhdnglglqqhqhqhqhqhqhqmyiyiyiyiyiyiyiyiywrvrvrvrvrvzttttfsfsfsfgkhkhkhkfuhuhlggggggggssfsfs

output:

45

result:

ok single line: '45'

Test #23:

score: 0
Accepted
time: 0ms
memory: 23416kb

input:

ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo

output:

2500

result:

ok single line: '2500'

Test #24:

score: 0
Accepted
time: 4ms
memory: 22324kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcpppppppppppppppppppppnuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu

output:

380

result:

ok single line: '380'

Test #25:

score: 0
Accepted
time: 0ms
memory: 21980kb

input:

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj

output:

2304

result:

ok single line: '2304'

Test #26:

score: 0
Accepted
time: 5ms
memory: 21704kb

input:

gggggggggtoooooooooccwwwwwwwwwwwwwwwwmllllllllllllllxvvjeeeppppppdnswwwwieeeeeeeeeeeeeeeeeeeesl

output:

110

result:

ok single line: '110'

Test #27:

score: 0
Accepted
time: 2ms
memory: 21924kb

input:

vlvivlvwvlvivlvkvlvivlvwvlvivlvfvlvivlvwvlvivlvkvlvivlvwvlvivlvzvlvivlvwvlvivlvkvlvivlvwvlvivlvfvlvi

output:

93

result:

ok single line: '93'

Test #28:

score: 0
Accepted
time: 0ms
memory: 21672kb

input:

nbnenbnjnbnenbnxnbnenbnjnbnenbnmnbnenbnjnbnenuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu

output:

729

result:

ok single line: '729'

Test #29:

score: 0
Accepted
time: 0ms
memory: 22020kb

input:

ydycydylydycydyodoycydylydycydybydyccccccccccccccccccccccdycydyxydycydylydycydyrydycydylydycydybydvq

output:

132

result:

ok single line: '132'

Test #30:

score: 0
Accepted
time: 0ms
memory: 22772kb

input:

dzydpxreexldgbslbouxllaizermiyzzmnawejbabckjdqybqwsaysietcsdfkclenvpkbsxhumglxvxmprkijakygjgjsbsawfj

output:

7

result:

ok single line: '7'

Test #31:

score: 0
Accepted
time: 0ms
memory: 22460kb

input:

bpmerpingvjipwmenzzalhrsmrkmxvmizieduxoxlxembhjjfrxsrecuhmntpwbjhxysmgrqvuqxhysalvpeurrkdifqloo

output:

8

result:

ok single line: '8'

Test #32:

score: 0
Accepted
time: 0ms
memory: 22400kb

input:

abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaab

output:

64

result:

ok single line: '64'

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #33:

score: 15
Accepted
time: 2ms
memory: 22828kb

input:

yhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyhyh...

output:

124251

result:

ok single line: '124251'

Test #34:

score: 0
Accepted
time: 2ms
memory: 22564kb

input:

nknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknknk...

output:

38226

result:

ok single line: '38226'

Test #35:

score: 0
Accepted
time: 5ms
memory: 23204kb

input:

oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

249500

result:

ok single line: '249500'

Test #36:

score: 0
Accepted
time: 0ms
memory: 23116kb

input:

ktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktktkokpkpkpkpkpkpjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjhtktpwuwuwuwuwuwuwuwuwuwuwuwiisisisisis...

output:

5778

result:

ok single line: '5778'

Test #37:

score: 0
Accepted
time: 3ms
memory: 22280kb

input:

gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

247506

result:

ok single line: '247506'

Test #38:

score: 0
Accepted
time: 5ms
memory: 21892kb

input:

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

248004

result:

ok single line: '248004'

Test #39:

score: 0
Accepted
time: 2ms
memory: 22612kb

input:

tdtytdtxtdtytdtptdtytdtxtdtytdtmtdtytdtxtdtytdtptdtytdtxtdtytdtbtdtytdtxtdtytdtptdtytdtxtdtytdtmtdtytdtxtdtytdtptdtytdtxtdtytdtztdtytdtxtdtytdtptdtytdtxtdtytdtmtdtytdtxtdtytdtptdtytdtxtdtytdtbtdtytdtxtdtytdtptdtytdtxtdtytdtmtdtytdtxtdtytdtptdtytdtxtdtytdtetdtytdtxtdtytdtptdtytdtxtdtytdtmtdtytdtxtdty...

output:

973

result:

ok single line: '973'

Test #40:

score: 0
Accepted
time: 0ms
memory: 23348kb

input:

xfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxfxf...

output:

123753

result:

ok single line: '123753'

Test #41:

score: 0
Accepted
time: 5ms
memory: 22056kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyybbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbgvgtgsgtgvgtgegtgvgtgygtgvgtgegtgvgtgngtgvgtgegtgvgtgygtgvgtgegtgvgtgbgtgvgtgegtgvgtgygtgvgtgegtgvgtgngtgvgtgegtgvgtgygtgvgtgegtgvgtgmgtgvgtgegtgvgtgygtgvgtgegtgvgtgngtgvgtgegtgv...

output:

2346

result:

ok single line: '2346'

Test #42:

score: 0
Accepted
time: 0ms
memory: 22376kb

input:

phxbzjihyzgshwcidlnkwkltarrnbvkgkzdakoyzeuhoeizcoemcdrtqrsesggbnvltdwrjahpekhylmtkwfcxrvgzdcarhtxkhejosurcntcgsycxkrkxspdqfcwiscudscsmfxjqxmxacgdzjupbaqbfzpsasyrvrpuhuusulurpmwfllpgbtgqnslvjupnpvgfvrdlowwsoaqsepmzdsirpmklgugblxexfxhtjigkhiwndihqsnowlrbyxeqczhyesczvuwthgvidmwtarmbokalyabzmdddcegplfpn...

output:

53

result:

ok single line: '53'

Test #43:

score: 0
Accepted
time: 0ms
memory: 21580kb

input:

nkevzhqlzcmqmbvtbojxbbtvgsxkbhyxrmwkzvvnvqppgbcgwplnupeizuimryoomumihznxizqcchutpzangopekbxirfgpunctyhdvkuhloshxnsmbyjtsdkevaaktccybajxmesubgmfennovcwlskuzjencrbafrzvgylsrzxpxvbrwapbkbqehtdopkgnvdifhkvtzbbjzdylautvnjqcmbrdyxpgsjtxptpayfyiyybkgvodovlvehskrvhtecinxbucymhucgudaujpcujdtgwdojjjvkewtjnghe...

output:

52

result:

ok single line: '52'

Test #44:

score: 0
Accepted
time: 3ms
memory: 21652kb

input:

abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...

output:

976

result:

ok single line: '976'

Subtask #3:

score: 24
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #45:

score: 24
Accepted
time: 4ms
memory: 22856kb

input:

lnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnlnln...

output:

12497500

result:

ok single line: '12497500'

Test #46:

score: 0
Accepted
time: 0ms
memory: 22084kb

input:

qhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqhqh...

output:

6481800

result:

ok single line: '6481800'

Test #47:

score: 0
Accepted
time: 9ms
memory: 21852kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

25000000

result:

ok single line: '25000000'

Test #48:

score: 0
Accepted
time: 3ms
memory: 23112kb

input:

ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

17816841

result:

ok single line: '17816841'

Test #49:

score: 0
Accepted
time: 8ms
memory: 21852kb

input:

xlxixlxpxlxixlxexlxixlxpxlxixlxgxlxixlxpxlxixlxexlxixlxpxlxixlxmxlxixlxpxlxixlxexlxixlxpxlxixlxgxlxixlxpxlxixlxexlxixlxpxlxixlxfxlxixlxpxlxixlxexlxixlxpxlxixlxgxlxixlxpxlxixlxexlxixlxpxlxixlxmxlxixlxpxlxixlxexlxixlxpxlxixlxgxlxixlxpxlxixlxexlxixlxpxlxixlxsxlxixlxpxlxixlxexlxixlxpxlxixlxgxlxixlxpxlxi...

output:

9945

result:

ok single line: '9945'

Test #50:

score: 0
Accepted
time: 4ms
memory: 21812kb

input:

elelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelel...

output:

504100

result:

ok single line: '504100'

Test #51:

score: 0
Accepted
time: 8ms
memory: 22976kb

input:

afamafacafamafakafamafacafamafaqafaanananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananana...

output:

1512930

result:

ok single line: '1512930'

Test #52:

score: 0
Accepted
time: 7ms
memory: 21808kb

input:

hmdqbxxvfzcxpohuffioztrgqgxkhfvtpgpudbbyaihadhzbeqrmjhljwmflxhhmrjqaumcacixjrcegaloxzzoprmnrzuldssiyuxfjtxsjjhvywupyviwunipmgxuqalcxatphosveipikcopziexcpspnidczvmupoxvabmlndxdrcrhdregvkqxnsjyfyvbqusygczosimhtjdbwwnlrqasixheataqyjwpxmrrkpxrvcbmkzbdafyahbzrhxkfbkfzrawufisbrdzfkdhuivwqueqlhisiwmahvagqn...

output:

413

result:

ok single line: '413'

Test #53:

score: 0
Accepted
time: 7ms
memory: 22576kb

input:

xznwghgyngrjehtffuiepaedcvdovapnjltjdavlxwmmcexbvxuhlohrfdjwnoimduzngahcupnwmuvqgyqutwaxzpxcqbvahcwwndugzesfkyhyxxehphrdhzucneyhdtlxhixdqrzmbtjxnatzjmwftvjknajzugquxubfmqvqxxqkpztyjfqsuzreyegwqvjbdqfzdjmctntsyjocdlxulnvqvxfjxdpefduawiosrekasgtqpnyhxuglvxorkqyemjkvcsimphvgwspqpaigfulymtkryxeibdilknxm...

output:

428

result:

ok single line: '428'

Test #54:

score: 0
Accepted
time: 8ms
memory: 23100kb

input:

abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...

output:

7232

result:

ok single line: '7232'

Subtask #4:

score: 26
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #55:

score: 26
Accepted
time: 34ms
memory: 22200kb

input:

bhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbhbh...

output:

1249925001

result:

ok single line: '1249925001'

Test #56:

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

input:

usususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususususus...

output:

396337935

result:

ok single line: '396337935'

Test #57:

score: 0
Accepted
time: 43ms
memory: 23304kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

2500050000

result:

ok single line: '2500050000'

Test #58:

score: 0
Accepted
time: 37ms
memory: 23244kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1016525689

result:

ok single line: '1016525689'

Test #59:

score: 0
Accepted
time: 43ms
memory: 21828kb

input:

kvkikvklkvkikvkgkvkikvklkvkikvkckvkikvklkvkikvkgkvkikvklkvkikvkakvkikvklkvkikvkgkvkikvklkvkikvkckvkikvklkvkikvkgkvkikvklkvkikvkxkvkikvklkvkikvkgkvkikvklkvkikvkckvkikvklkvkikvkgkvkikvklkvkikvkakvkikvklkvkikvkgkvkikvklkvkikvkckvkikvklkvkikvkgkvkikvklkvkikvkhkvkikvklkvkikvkgkvkikvklkvkikvkckvkikvklkvki...

output:

99645

result:

ok single line: '99645'

Test #60:

score: 0
Accepted
time: 39ms
memory: 22220kb

input:

pqpzpqpupqpzpqpbpqpzpqpupqpzpqpwpqpzpqpupqpzpqpbpqpzpqpupqpzpqpipqpzpqpupqpzpqpbpqpzpqpupqpzpqpwpqpzpqpupqpzpqpbpqpzpqpupqpzpqpspqpzpqpupqpzpqpbpqpzpqpupqpzpqpwpqpzpqpupqpzpqpbpqpzpqpupqpzpqpipqpzpqpupqpzpqpbpqpzpqpupqpzpqpwpqpzpqpupqpzpqpbpqpzpqpupqpzpqpgpqpzpqpupqpzpqpbpqpzpqpupqpzpqpwpqpzpqpupqpz...

output:

78569380

result:

ok single line: '78569380'

Test #61:

score: 0
Accepted
time: 39ms
memory: 22648kb

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

82810000

result:

ok single line: '82810000'

Test #62:

score: 0
Accepted
time: 25ms
memory: 22192kb

input:

vmlqjhjiwwzijupbzztlkcxbcdavxyqryzttbvvwwekgresldvhrtwwzkgldqvmtecanlhirufqzzvfoybnqorcgmpzhkedhxelbfgkdrktqblcsfngtmhpijdbmtznvmatyrwrbjkmmtgbbwhsiacswcuvszlwgveqehiudnnnuetqucajijlzcomkqfvhaukpnzwlrysonewxfopijuyatwmpslwelwljnkyiibdeuvernjqizvzmtutgsvzdjfksyghkmbqimxarcmkerlbrxnfehzpbmzrvzbjhetlgv...

output:

3989

result:

ok single line: '3989'

Test #63:

score: 0
Accepted
time: 35ms
memory: 23324kb

input:

bcqqtvvdvexrttkgcbhmlhoasnlcektbxssxkxyavuqritimuzvnaurotozfdfglteetpbnpuvymvaghqzqznontyyxciqbglyaedgnzxjzmvampibduzoypreeconehptujqukxezbdcmcguzxgeqzsuqrrhtiudmeqflamybdebwpdkgohesfmbzemzojexzcljvcopvtvlovbngdvhxcshgbwcaluonvfzlaloirqpqqpnbhbbhvyizecupuoyhmcfbobawpqlwmtornvtipqsfphujgltwmodxdcwfpg...

output:

125529616

result:

ok single line: '125529616'

Test #64:

score: 0
Accepted
time: 34ms
memory: 22900kb

input:

abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...

output:

66664

result:

ok single line: '66664'

Subtask #5:

score: 27
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #65:

score: 27
Accepted
time: 110ms
memory: 23096kb

input:

bnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbnbn...

output:

11250075000

result:

ok single line: '11250075000'

Test #66:

score: 0
Accepted
time: 107ms
memory: 21804kb

input:

jzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjzjz...

output:

894243195

result:

ok single line: '894243195'

Test #67:

score: 0
Accepted
time: 111ms
memory: 22680kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

22499400004

result:

ok single line: '22499400004'

Test #68:

score: 0
Accepted
time: 118ms
memory: 22580kb

input:

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

2958163321

result:

ok single line: '2958163321'

Test #69:

score: 0
Accepted
time: 147ms
memory: 21780kb

input:

xqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxexqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxyxqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxexqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxsxqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxexqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxyxqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxexqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxvxqxtxqxwxqxtxqxlxqxtxqxwxqxtxqxexqxtxqxwxqxt...

output:

298935

result:

ok single line: '298935'

Test #70:

score: 0
Accepted
time: 112ms
memory: 23012kb

input:

zwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzwzw...

output:

1210831209

result:

ok single line: '1210831209'

Test #71:

score: 0
Accepted
time: 117ms
memory: 22212kb

input:

hyhnhyhehyhnhyhlhyhnhyhehyhnhyhkhyhnhyhehyhnhyhlhyhnhyhehyhnhyhdhyhnhyhehyhnhyhlhyhnhyhehyhnhyhkhyhnhyhehyhnhyhlhyhnhyhehyhnhyhwhyhnhyhehyhnhyhlhyhnhyhehyhnhyhkhyhnhyhehyhnhyhlhyhnhyhehyhnhyhdhyhnhyhehyhnhyhlhyhnhyhehyhnhyhkhyhnhyhehyhnhyhlhyhnhyhehyhnhyhvhyhnhyhehyhnhyhlhyhnhyhehyhnhyhkhyhnhyhehyhn...

output:

303195156

result:

ok single line: '303195156'

Test #72:

score: 0
Accepted
time: 101ms
memory: 22808kb

input:

hnrootvymrwweaxjusfltkgyqyeioonpksxtampxsamlfcitaauwcjfmxbtvghsyswjyaephlciqgpdwvqnkdhtzkqmyuqukbsobqrpuowsyspglpdypcejwdvolfyezxpjyjztwgcgudvrtsdxouampqybzqtoosumwzwsgboqbgpdycknpatsirizrqioxoxdjfxwdvnqixhlstcrvrkpvazncakguavcbjazssqsfbnrdrhdlozsohomcpannklcxcluhcjvumhfntubbqwnmeosusnoopqicougnnpxc...

output:

11804

result:

ok single line: '11804'

Test #73:

score: 0
Accepted
time: 103ms
memory: 22224kb

input:

yoljcehfgzraqykusrdwgqxdudzvepmjvrsfoosapcxoxoqzfaebohkstrtgnawnonwuynojpzulyulmlxfzbdmqeofumicjihysfofcyfhnsjurggtonwstxatbpoffhamgqkktzdphibrpeiiledjizhvrcnywcyyhvujhqvhvsyxkifcizpczjawdwuxkrxcmkqbsrlbrorrcyznwzpcejgrryyxnursejnogvjlehfspyutfnbmjniaaxtsfmnsvsebwotxqempvqreeeslrxwlljwsawxkktdayuumi...

output:

11813

result:

ok single line: '11813'

Test #74:

score: 0
Accepted
time: 146ms
memory: 22612kb

input:

abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...

output:

262144

result:

ok single line: '262144'

Test #75:

score: 0
Accepted
time: 111ms
memory: 22748kb

input:

acbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabcacbabc...

output:

3750025000

result:

ok single line: '3750025000'

Test #76:

score: 0
Accepted
time: 148ms
memory: 21920kb

input:

uptvtysodzujkjcvrzkzydggrhjjlicywbakjpulmdqnlhzqbyhbblhzemftazrldvrxmfuiejvuxvevvescgolivepuwbdyyiylvtqubxfrnmouoshonhbwojudfexgnafvjxrogotuomkwlyoafqsqrzmomodmkxuguysscbidukwlblzrsyqdjsoaqfplvhmqhhpgkvztkpiwowfmjtujkzpileosqqsskywfnvaqhprbhcyfvbzrtkkjmbvxzqgfdoelxzecvgnsxiuvmassxzmweiixxppvmmbxvgol...

output:

184796836

result:

ok single line: '184796836'