QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181332#5256. Insertionsucup-team1209#AC ✓16ms9124kbC++209.2kb2023-09-16 17:47:572023-09-16 17:47:58

Judging History

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

  • [2023-09-16 17:47:58]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:9124kb
  • [2023-09-16 17:47:57]
  • 提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ; 
using ll = long long;
cs int N = 1e5 + 5;

char S[N], T[N], P[N];
int n, m, k; 


void work_skip(char *T, char *P, vector <bool> & mat) {
    // mat[i] P[i, k] ~ T 
    
    string S = " " + string(T + 1) + string(P + 1);   
    int l = S.length() - 1; 
    vector <int> lcp(l + 1);
    int mx = 1, pt = 1; 
    lcp[1] = l; 
    for(int i = 2; i <= l; i++) {
        if(i <= mx) lcp[i] = min(lcp[i - pt + 1], mx - i + 1);
        while(i + lcp[i] <= l && S[i + lcp[i]] == S[1 + lcp[i]]) ++ lcp[i];
        if(i + lcp[i] - 1 > mx) pt = i, mx = i + lcp[i] - 1; 
    }
    for(int i = 1; i <= k; i++) {
        if(lcp[i + m] >= m) mat[i] = 1; 
    }
}

void work_mat(char *T, char *P, vector <bool> & mat) {
    // mat[i] P[i, k] ~ T 
    
    string S = " " + string(T + 1) + string(P + 1);   
    int l = S.length() - 1; 
    vector <int> lcp(l + 1);
    int mx = 1, pt = 1; 
    lcp[1] = l; 
    for(int i = 2; i <= l; i++) {
        if(i <= mx) lcp[i] = min(lcp[i - pt + 1], mx - i + 1);
        while(i + lcp[i] <= l && S[i + lcp[i]] == S[1 + lcp[i]]) ++ lcp[i];
        if(i + lcp[i] - 1 > mx) pt = i, mx = i + lcp[i] - 1; 
    }
    for(int i = 1; i <= k; i++) {
        if(lcp[i + m] == k - i + 1) mat[i] = 1; 
    }
}
int run(char *T, char *P) {
    vector <int> nxt(k + 1);
    for(int i = 2, j = 0; i <= k; i++) {
        while(j && P[j + 1] != P[i]) j = nxt[j];
        if(P[j + 1] == P[i]) ++ j;
        nxt[i] = j; 
    }
    int ans = 0, p = 0; 
    for(int i = 1; i <= m; i++) {
        while(p && T[i] != P[p + 1]) p = nxt[p];
        if(T[i] == P[p + 1]) ++ p; 
        if(p == k) ++ ans, p = nxt[p];
    }
    return ans; 
}
void work(char *S, char *T, char *P, vector <int> & ans, vector <bool> & mat, vector <int> & nxt, vector <int> & pnt) {
    //mat[i] P [i, k] ~ T 
    vector <int> sum(k + 1);
    for(int i = 2, j = 0; i <= k; i++) {
        while(j && P[j + 1] != P[i]) j = nxt[j];
        if(P[j + 1] == P[i]) ++ j;
        nxt[i] = j; 
    }
    for(int i = 1; i < k; i++) {
        sum[i] = sum[nxt[i]];
        if(i + m >= k) sum[i] += mat[i + 1];
    }
    int p = 0; 
    int fix = 0; 
    for(int i = 1; i <= n; i++) {
        while(p && S[i] != P[p + 1]) p = nxt[p];
        if(S[i] == P[p + 1]) ++ p; 
        if(p == k) {
            ++ fix;
            p = nxt[p];
        }
        ans[i] += fix + sum[p];
        pnt[i] = p; 
    }
}

void build_tree(vector <int> nxt, vector <int> & top, vector <int> & d) {
    for(int i = 1; i <= k; i++) {
        if(!nxt[i]) {
            d[i] = i; 
            top[i] = 0; 
        }
        if(nxt[i]) {
            if(i - nxt[i] == d[nxt[i]]) {
                d[i] = d[nxt[i]];
                top[i] = top[nxt[i]];
            }
            else {
                d[i] = i - nxt[i];
                top[i] = nxt[i];
            }
        }
    }
}

struct dat {
    int l, r, d; 
}; 

vector <dat> cat(int p, cs vector <int> & top, cs vector <int> & d) {
    vector <dat> c; 
    while(p) {
        int x = top[p];
        c.pb({x + d[p], p, d[p]});
        p = x; 
    }
    return c; 
}

void exgcd(int a, int b, int & x, int & y) {
    if(!b) {
        return x = 1, y = 0, void();
    }
    exgcd(b, a % b, y, x); 
    y -= a / b * x; 
}

int pbpb(int s, int len1, int d1, int len2, int d2) {
    // int l0 = 0, r0 = (len1 - 1) / d1 * d1;
    // int l1 = 0, r1 = (len2 - 1) / d2 * d2;
    // std::swap(l1 = s - l1, r1 = s - r1);
    
    // int gcd = std::__gcd(d1, d2);
    // ll lcm = d1 / gcd * (ll) d2;
    // if(l0 % gcd != l1 % gcd) {
    //     return 0;
    // }
    // if(l1 < 0) {
    //     l1 %= d2;
    //     if(l1 < 0) l1 += d2;
    // }
    // {
    //     int u, v;
    //     exgcd(d1, d2, u, v);
    //     int w = len1 - len2;
    // }
    // if(l1) l1 = (l1 - 1) / lcm * lcm + lcm;
    // r0 = min(r0, r1);
    // if(r0 < l1) return 0;
    // return 1 + (r0 - l1) / lcm;


    len1 = (len1 - 1) / d1; 
    len2 = (len2 - 1) / d2;  
    int x = 0, y = 0; 
    // x * d1 + y * d2 == s 
    exgcd(d1, d2, x, y);
    int d = __gcd(d1, d2); 
    // x * d1 + y * d2 == gcd(d1, d2) = d
    if(s % d) return 0; 
    x *= s / d; 
    y *= s / d; 
    // assert(x * d1 + y * d2 == s);
    // cerr << "FFFFFFF " << x << ' ' << y << ' ' << d1 << ' ' << d2 << ' ' << s << endl;
    // cerr << len1 << ' ' << len2 << endl;
    d1 /= d; 
    d2 /= d; 
    if(x < 0) { 
        int t = (-x) / d2; 
        x += t * d2; 
        y -= t * d1;
    } 
    if(x < 0) {
        x += d2; 
        y -= d1; 
    }
    int t = x / d2; 
    x -= t * d2; 
    y += t * d1; 
    if(x < 0) return 0; 
    if(y < 0) return 0;
    if(x > len1) return 0; 

    // cerr << "FFFFFFF " << x << ' ' << y << ' ' << d1 << ' ' << d2 << ' ' << s << endl;
    // cerr << len1 << ' ' << len2 << endl;

    int lp = 0; 
    if(y > len2) {
        lp = (y - len2 - 1) / d1 + 1; 
    }
    int rp = (len1 - x) / d2;
    rp = min(rp, y / d1);
    // cerr << lp << ' ' << rp << endl;
    return max(0, rp - lp + 1);
    // int ans = 0; 
    // while(1) {
    //     if(y < 0) break;
    //     if(x > len1) break;
    //     if(y <= len2) ++ ans; 
    //     x += d2; 
    //     y -= d1;
    // }
    // return ans; 
}

int fuck(dat a, dat b) {
    auto [l1, r1, d1] = a; 
    auto [l2, r2, d2] = b; 
    int len1 = r1 - l1 + 1;
    int len2 = r2 - l2 + 1;
    int ans = 0; 
    int s = k - m - l1 - l2;


    // for(int i = 0; i < len1; i += d1) 
    // for(int j = 0; j < len2; j += d2) {
    //     if(i + j == s) ++ ans; // , cout <<i << ' ' <<j <<endl;
    // }
    // if(ans != pbpb(s, len1, d1, len2, d2)) {
    //     cout << s << ' '<< len1 << ' ' << d1 << ' ' << len2 << ' ' << d2 << ' ' << ans << endl;
    //     cout << pbpb(s, len1, d1, len2, d2) << '\n';
    //     assert(0);
    // }
    return pbpb(s, len1, d1, len2, d2);
}

int calc(int p1, int p2, cs vector <int> & top1, cs vector <int> & d1, cs vector <int> & top2, cs vector <int> & d2) {
    vector <dat> c1 = cat(p1, top1, d1); 
    vector <dat> c2 = cat(p2, top2, d2);
    int ans = 0; 
    for(auto a : c1) for(auto b : c2) ans += fuck(a, b);
    return ans; 
}

void skip(vector <int> & ans, vector <int> t2, vector <int> pnt) {
    vector <bool> mat(k + 1);
    work_skip(T, P, mat);
    vector <int> nxt(k + 1);
    for(int i = 2, j = 0; i <= k; i++) {
        while(j && P[j + 1] != P[i]) j = nxt[j];
        if(P[j + 1] == P[i]) ++ j;
        nxt[i] = j; 
    }
    vector <int> t1(k + 1);
    for(int i = 1; i <= k; i++) {
        if(!mat[nxt[i] + 1]) {
            t1[i] = t1[nxt[i]];
        }
        else {
            t1[i] = nxt[i];
        }
    }
    vector <int> top1(k + 1), d1(k + 1);
    vector <int> top2(k + 1), d2(k + 1);
    build_tree(t1, top1, d1);
    build_tree(t2, top2, d2);

    int p = 0; 
    for(int i = 1; i < n; i++) {
        while(p && S[i] != P[p + 1]) p = nxt[p];
        if(S[i] == P[p + 1]) ++ p; 
        if(p == k) {
            p = nxt[p];
        }
        int fucku = mat[p + 1] ? p : t1[p];
        // cout << "FFdsafasfasdfasfd " << i << ' ' << fucku <<' ' << pnt[n - i] << endl;
        ans[i] += calc(fucku, pnt[n - i], top1, d1, top2, d2);
    }
}

void output(vector <int> ans) {
    int mx = 0, cnt = 0;
    int lp = n, rp = 0;  
    for(int i = 0; i <= n; i++) {
        if(ans[i] > mx) {
            mx = ans[i];
            cnt = 1; 
        }
        else if(ans[i] == mx) {
            cnt ++; 
        }
    }
    for(int i = 0; i <= n; i++) 
    if(ans[i] == mx) {
        lp = min(lp, i);
        rp = max(rp, i);
    }
    // for(int i = 0; i <= n; i++)
    //     cout << ans[i] << ' ';
    // cout << endl;
    cout << mx << ' ' << cnt << ' ' << lp << ' ' << rp << '\n';
}

void Main() {
    scanf("%s%s%s", S + 1, T + 1, P + 1);
    n = strlen(S + 1);
    m = strlen(T + 1);
    k = strlen(P + 1);
    vector <int> nxt(k + 1);
    vector <int> pnt(n + 1);
    vector <int> ans1(n + 1); 
    vector <bool> mat1(k + 1);
    work_mat(T, P, mat1); 
    work(S, T, P, ans1, mat1, nxt, pnt);
    // for(int x : ans1) cout << x << ' '; cout << endl;
    reverse(S + 1, S + n + 1); 
    reverse(T + 1, T + m + 1);
    reverse(P + 1, P + k + 1);
    vector <int> ans2(n + 1);
    vector <bool> mat2(k + 1);
    work_mat(T, P, mat2); 
    work(S, T, P, ans2, mat2, nxt, pnt);
    // for(int x : ans2) cout << x << ' '; cout << endl;
    reverse(S + 1, S + n + 1); 
    reverse(T + 1, T + m + 1);
    reverse(P + 1, P + k + 1);
    
    vector <int> ans(n + 1);
    for(int i = 0; i <= n; i++) 
        ans[i] = ans1[i] + ans2[n - i];
    int bonus = run(T, P);
    // cout << "FFF " << bonus << endl;
    for(int i = 0; i <= n; i++)
        ans[i] += bonus; 
    if(m >= k) {
        output(ans);
        return;
    }
    vector <int> ans3(n + 1);
    skip(ans3, nxt, pnt);
    // for(int x : ans3) cout << x << ' '; cout << endl;
    for(int i = 0; i <= n; i++)
        ans[i] += ans3[i];
    output(ans);
}



int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    Main();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3700kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

ok 4 number(s): "2 2 6 7"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

z
zzkkzzkk
z

output:

5 2 0 1

result:

ok 4 number(s): "5 2 0 1"

Test #3:

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

input:

wgwwggggw
g
gggg

output:

2 5 4 8

result:

ok 4 number(s): "2 5 4 8"

Test #4:

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

input:

q
uuquu
u

output:

4 2 0 1

result:

ok 4 number(s): "4 2 0 1"

Test #5:

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

input:

gpgggpppg
pg
gpgg

output:

2 1 4 4

result:

ok 4 number(s): "2 1 4 4"

Test #6:

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

input:

p
xpxp
p

output:

3 2 0 1

result:

ok 4 number(s): "3 2 0 1"

Test #7:

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

input:

aacaacacaa
ca
caca

output:

2 5 2 9

result:

ok 4 number(s): "2 5 2 9"

Test #8:

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

input:

k
kekekkekk
k

output:

7 2 0 1

result:

ok 4 number(s): "7 2 0 1"

Test #9:

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

input:

ghhhhg
g
ghhg

output:

2 1 3 3

result:

ok 4 number(s): "2 1 3 3"

Test #10:

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

input:

b
xbb
b

output:

3 2 0 1

result:

ok 4 number(s): "3 2 0 1"

Test #11:

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

input:

nddnnndndn
dnd
ndndn

output:

3 1 5 5

result:

ok 4 number(s): "3 1 5 5"

Test #12:

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

input:

imiimmmm
miimi
i

output:

6 9 0 8

result:

ok 4 number(s): "6 9 0 8"

Test #13:

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

input:

gzzzzzzzzz
zgzzzg
gzgggzzz

output:

0 11 0 10

result:

ok 4 number(s): "0 11 0 10"

Test #14:

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

input:

m
mmwmwmw
wwmww

output:

0 2 0 1

result:

ok 4 number(s): "0 2 0 1"

Test #15:

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

input:

jmmmmjmmj
jmjjjmjm
mjmmmmjj

output:

0 10 0 9

result:

ok 4 number(s): "0 10 0 9"

Test #16:

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

input:

f
ffffwff
wffw

output:

0 2 0 1

result:

ok 4 number(s): "0 2 0 1"

Test #17:

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

input:

plpll
llplll
pppppppl

output:

0 6 0 5

result:

ok 4 number(s): "0 6 0 5"

Test #18:

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

input:

yypppypyy
ppyyypppy
ypyppypp

output:

0 10 0 9

result:

ok 4 number(s): "0 10 0 9"

Test #19:

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

input:

okkkkkok
okokkkoo
kookooko

output:

0 9 0 8

result:

ok 4 number(s): "0 9 0 8"

Test #20:

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

input:

ccc
cpppp
cc

output:

3 1 3 3

result:

ok 4 number(s): "3 1 3 3"

Test #21:

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

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

631 1000 0 999

result:

ok 4 number(s): "631 1000 0 999"

Test #22:

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

input:

annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...

output:

0 1000 0 999

result:

ok 4 number(s): "0 1000 0 999"

Test #23:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...

output:

0 1000 0 999

result:

ok 4 number(s): "0 1000 0 999"

Test #24:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 413 587 999

result:

ok 4 number(s): "1 413 587 999"

Test #25:

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

input:

rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...

output:

315 2 1 998

result:

ok 4 number(s): "315 2 1 998"

Test #26:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...

output:

260 1 113 113

result:

ok 4 number(s): "260 1 113 113"

Test #27:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

748 907 0 906

result:

ok 4 number(s): "748 907 0 906"

Test #28:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...

output:

0 907 0 906

result:

ok 4 number(s): "0 907 0 906"

Test #29:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...

output:

0 907 0 906

result:

ok 4 number(s): "0 907 0 906"

Test #30:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

1 702 0 701

result:

ok 4 number(s): "1 702 0 701"

Test #31:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...

output:

374 454 0 906

result:

ok 4 number(s): "374 454 0 906"

Test #32:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...

output:

291 370 50 788

result:

ok 4 number(s): "291 370 50 788"

Test #33:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

937 966 0 965

result:

ok 4 number(s): "937 966 0 965"

Test #34:

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

input:

apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...

output:

35 64 600 663

result:

ok 4 number(s): "35 64 600 663"

Test #35:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...

output:

0 966 0 965

result:

ok 4 number(s): "0 966 0 965"

Test #36:

score: 0
Accepted
time: 1ms
memory: 3980kb

input:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

1 768 0 767

result:

ok 4 number(s): "1 768 0 767"

Test #37:

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

input:

jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...

output:

468 483 0 964

result:

ok 4 number(s): "468 483 0 964"

Test #38:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...

output:

429 443 80 964

result:

ok 4 number(s): "429 443 80 964"

Test #39:

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

input:

tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

44459 99774 0 99773

result:

ok 4 number(s): "44459 99774 0 99773"

Test #40:

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

input:

annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...

output:

0 99774 0 99773

result:

ok 4 number(s): "0 99774 0 99773"

Test #41:

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

input:

eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...

output:

0 99774 0 99773

result:

ok 4 number(s): "0 99774 0 99773"

Test #42:

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

input:

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1 61041 38733 99773

result:

ok 4 number(s): "1 61041 38733 99773"

Test #43:

score: 0
Accepted
time: 10ms
memory: 9068kb

input:

zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...

output:

22229 2 1 99772

result:

ok 4 number(s): "22229 2 1 99772"

Test #44:

score: 0
Accepted
time: 15ms
memory: 9024kb

input:

babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...

output:

22229 2 1 99772

result:

ok 4 number(s): "22229 2 1 99772"

Test #45:

score: 0
Accepted
time: 6ms
memory: 9004kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

85548 90750 0 90749

result:

ok 4 number(s): "85548 90750 0 90749"

Test #46:

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

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...

output:

0 90750 0 90749

result:

ok 4 number(s): "0 90750 0 90749"

Test #47:

score: 0
Accepted
time: 16ms
memory: 8928kb

input:

llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...

output:

0 90750 0 90749

result:

ok 4 number(s): "0 90750 0 90749"

Test #48:

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

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1 71220 19530 90749

result:

ok 4 number(s): "1 71220 19530 90749"

Test #49:

score: 0
Accepted
time: 11ms
memory: 8932kb

input:

qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...

output:

42774 45375 0 90748

result:

ok 4 number(s): "42774 45375 0 90748"

Test #50:

score: 0
Accepted
time: 12ms
memory: 9048kb

input:

xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...

output:

40492 43093 2508 88692

result:

ok 4 number(s): "40492 43093 2508 88692"

Test #51:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

97181 91251 0 91250

result:

ok 4 number(s): "97181 91251 0 91250"

Test #52:

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

input:

vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

6028 98 22809 22906

result:

ok 4 number(s): "6028 98 22809 22906"

Test #53:

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

input:

qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...

output:

0 91251 0 91250

result:

ok 4 number(s): "0 91251 0 91250"

Test #54:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 4772 86479 91250

result:

ok 4 number(s): "1 4772 86479 91250"

Test #55:

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

input:

lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...

output:

48590 45626 0 91250

result:

ok 4 number(s): "48590 45626 0 91250"

Test #56:

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

input:

ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...

output:

22317 19352 36850 75552

result:

ok 4 number(s): "22317 19352 36850 75552"

Test #57:

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

input:

abbababa
babbba
bbab

output:

2 6 1 7

result:

ok 4 number(s): "2 6 1 7"

Test #58:

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

input:

ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba
aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab
abbbbaabaa

output:

1 7 43 99

result:

ok 4 number(s): "1 7 43 99"