QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268672 | #5256. Insertions | DeepSea | AC ✓ | 20ms | 29968kb | C++17 | 4.3kb | 2023-11-28 19:36:27 | 2023-11-28 19:36:28 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define rep(i,x,y) for(auto i(x);i<=(y);++i)
#define Rep(i,x,y) for(auto i(x);i>=(y);--i)
using namespace std;
namespace KMP {
vector<int> getfail (string s,int siz) {
vector<int> nxt(siz + 1) ;
int j = nxt[1] = 0 ;
rep (i,2,siz) {
while (j && s[j + 1] != s[i]) j = nxt[j] ;
if (s[j + 1] == s[i]) ++ j ;
nxt[i] = j;
}
return nxt;
}
}
int tim = 0 ;
struct failtree {
const int siz;
vector <int> fail ;
vector<vector<int>> ed ;
failtree(vector<int>_fail) : siz((int)_fail.size( ) - 1) , fail(_fail) {
ed.resize(siz + 1) ;
rep (i,1,siz) {
ed [fail[i]].emplace_back (i) ;
}
rep (i,0,siz) ed[i].shrink_to_fit( ) ;
}
inline void dfs(int u,vector<int> &St,vector<int> &Ed) {
St[u] = ++ tim ;
for (int v:ed[u]) {
dfs(v,St,Ed) ;
}
Ed[u] = tim ;
}
void getdfn (vector<int> &St,vector<int> &Ed) {
tim = 0 ;
St.resize(siz + 1) , Ed.resize(siz + 1) ;
dfs(0,St,Ed) ;
}
} ;
signed main ( ) {
ios::sync_with_stdio (false) , cin.tie (0) , cout.tie (0) ;
string s,o,t,ro,rt;
int n , m , l ;
cin >> s >> o >> t ; ro = o ; reverse(all(ro)) ; rt = t ; reverse (all(rt)) ;
n = s.size( ) , m = o.size( ) , l = t.size( ) ;
auto index1=[](string &str) {str="<"+str+">";};
index1 (s) ; index1(o) ; index1 (t) ; index1(ro) ; index1(rt) ;
failtree ft(KMP::getfail(t,l)),frt(KMP::getfail(rt,l));
vector<int>ans(n+2),sufp(n+2),cnt1(l+1),cnt2(l+1),pres(n+1),st,ed,pos,nxto=KMP::getfail(o,m);
vector<bool>TinS(n+1),TsufO(m+1),TpreO(m+1),OinT(l+1);
int TinO = 0 , j = 0 ;
rep (i,1,n) {
while (j && t[j + 1] != s[i]) j = ft.fail [j] ;
if (t[ j + 1 ] == s[i]) ++ j ;
if (j == l) TinS[i - l + 1] = 1 ;
}
j = 0 ;
rep (i,1,m) {
while (j && t[j + 1] != o[i]) j = ft.fail [j] ;
if (t[ j + 1 ] == o[i]) ++ j ;
if (j == l) TinO ++ ;
}
if (j == m) j = ft.fail[j] ;
while (j) {
TsufO[m - j + 1] = 1 ;
j = ft.fail[j] ;
}
j = 0 ;
Rep (i,m,1) {
while (j && rt[j + 1] != o[i]) j = frt.fail [j] ;
if (rt[j + 1] == o[i]) ++ j ;
}
if (j == m) j = frt.fail[j] ;
while (j) {
TpreO[j] = 1 ;
j = frt.fail[j] ;
}
if (m < l) {
j = 0 ;
rep (i,1,l) {
while (j && o[j + 1] != t[i]) j = nxto[j] ;
if (o[j + 1] == t[i]) ++ j ;
if (j == m) OinT[i - m + 1] = 1;
}
}
rep(i,1,n) pres[i] = pres[i - 1] + TinS[i];
rep(i,1,n + 1) {
ans[i] = pres[n] - pres[i - 1] + TinO ;
if (i - l >= 0) {
ans[i] += pres[i - l] ;
}
}
pres.clear( ); pres.shrink_to_fit();
TinS.clear( ); TinS.shrink_to_fit();
rep (i,1,l) {
if (l - i <= m && l != i) cnt2[i] = TsufO[m - (l - i) + 1] ;
if (l - i <= m) cnt1[i] = TpreO[l - i] ;
cnt2[i] += cnt2 [ frt.fail[i] ] ;
cnt1[i] += cnt1 [ ft.fail[i] ] ;
}
j = 0 ;
Rep (i,n,1) {
while (j && rt[j + 1] != s[i]) j = frt.fail[j] ;
if (rt[j + 1] == s[i]) ++ j ;
sufp[i] = j ;
ans[i] += cnt2 [j] ;
}
frt.getdfn (st , ed) ;
struct bit {
vector<int> t;
inline void add (int l,int r,int c) {
for (l ++ ; l < t.size(); l += l & -l) t[l] += c;
for (r ++ ; r < t.size(); r += r & -r) t[r] -= c;
}
inline int qry (int p,int c = 0) {
for (p ++ ; p ; p &= p - 1) c += t[p] ;
return c;
}
}T;
T.t.resize(l + 3);
auto ins = [&] (int x) {
if (x<l&&OinT[x + 1]) {
T.add (st[l - x - m] , ed[l - x - m] + 1 , 1) ;
}
} ;
auto del = [&] (int x) {
if (x<l&&OinT[x + 1]) {
T.add (st[l - x - m] , ed[l - x - m] + 1 , -1) ;
}
} ;
j = 0 ;
vector <vector<int>> qat(l + 1) ;
rep (i,1,n + 1) {
ans[i] += cnt1[j] ;
qat [j].emplace_back (i) ;
if (i == n + 1) break ;
while (j && s[i] != t[j + 1]) j = ft.fail[j] ;
if (s[i] == t[j + 1]) {
++ j ;
}
}
rep (i,0,l) qat[i].shrink_to_fit( ) ;
function<void(int)> dfs = [&](int u) {
ins (u) ;
for (int qr : qat[u]) ans [qr] += T.qry (st[sufp[qr]]);
for (int v : ft.ed[u]) dfs (v) ;
del(u) ;
} ;
dfs(0) ;
int mx = 0 ;
rep (i,1,n + 1) {
if (ans[i] > mx) {
mx = ans[i] ;
pos.clear ( ) ;
}
if (ans[i] == mx) {
pos.emplace_back (i - 1) ;
}
}
cout << mx << ' ' << pos.size( ) << ' ' << pos.front ( ) << ' ' << pos.back ( ) << '\n' ;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3456kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3404kb
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: 3472kb
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: 3432kb
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: 3404kb
input:
gpgggpppg pg gpgg
output:
2 1 4 4
result:
ok 4 number(s): "2 1 4 4"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
p xpxp p
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3484kb
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: 3436kb
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: 3404kb
input:
ghhhhg g ghhg
output:
2 1 3 3
result:
ok 4 number(s): "2 1 3 3"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3396kb
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: 3436kb
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: 3480kb
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: 3440kb
input:
gzzzzzzzzz zgzzzg gzgggzzz
output:
0 11 0 10
result:
ok 4 number(s): "0 11 0 10"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3512kb
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: 3424kb
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: 3416kb
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: 3396kb
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: 3424kb
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: 3456kb
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: 3436kb
input:
ccc cpppp cc
output:
3 1 3 3
result:
ok 4 number(s): "3 1 3 3"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
631 1000 0 999
result:
ok 4 number(s): "631 1000 0 999"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 413 587 999
result:
ok 4 number(s): "1 413 587 999"
Test #25:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...
output:
315 2 1 998
result:
ok 4 number(s): "315 2 1 998"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...
output:
260 1 113 113
result:
ok 4 number(s): "260 1 113 113"
Test #27:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
748 907 0 906
result:
ok 4 number(s): "748 907 0 906"
Test #28:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #29:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3704kb
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: 3684kb
input:
kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...
output:
291 370 50 788
result:
ok 4 number(s): "291 370 50 788"
Test #33:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
937 966 0 965
result:
ok 4 number(s): "937 966 0 965"
Test #34:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...
output:
35 64 600 663
result:
ok 4 number(s): "35 64 600 663"
Test #35:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...
output:
0 966 0 965
result:
ok 4 number(s): "0 966 0 965"
Test #36:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...
output:
1 768 0 767
result:
ok 4 number(s): "1 768 0 767"
Test #37:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...
output:
468 483 0 964
result:
ok 4 number(s): "468 483 0 964"
Test #38:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...
output:
429 443 80 964
result:
ok 4 number(s): "429 443 80 964"
Test #39:
score: 0
Accepted
time: 7ms
memory: 29968kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
44459 99774 0 99773
result:
ok 4 number(s): "44459 99774 0 99773"
Test #40:
score: 0
Accepted
time: 11ms
memory: 27344kb
input:
annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #41:
score: 0
Accepted
time: 7ms
memory: 16192kb
input:
eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #42:
score: 0
Accepted
time: 14ms
memory: 22784kb
input:
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
1 61041 38733 99773
result:
ok 4 number(s): "1 61041 38733 99773"
Test #43:
score: 0
Accepted
time: 16ms
memory: 25952kb
input:
zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #44:
score: 0
Accepted
time: 20ms
memory: 25932kb
input:
babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #45:
score: 0
Accepted
time: 16ms
memory: 28980kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
85548 90750 0 90749
result:
ok 4 number(s): "85548 90750 0 90749"
Test #46:
score: 0
Accepted
time: 13ms
memory: 26644kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #47:
score: 0
Accepted
time: 11ms
memory: 15672kb
input:
llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #48:
score: 0
Accepted
time: 14ms
memory: 22812kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
1 71220 19530 90749
result:
ok 4 number(s): "1 71220 19530 90749"
Test #49:
score: 0
Accepted
time: 15ms
memory: 25656kb
input:
qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...
output:
42774 45375 0 90748
result:
ok 4 number(s): "42774 45375 0 90748"
Test #50:
score: 0
Accepted
time: 9ms
memory: 25648kb
input:
xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...
output:
40492 43093 2508 88692
result:
ok 4 number(s): "40492 43093 2508 88692"
Test #51:
score: 0
Accepted
time: 18ms
memory: 26228kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
97181 91251 0 91250
result:
ok 4 number(s): "97181 91251 0 91250"
Test #52:
score: 0
Accepted
time: 3ms
memory: 23260kb
input:
vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
6028 98 22809 22906
result:
ok 4 number(s): "6028 98 22809 22906"
Test #53:
score: 0
Accepted
time: 14ms
memory: 14488kb
input:
qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...
output:
0 91251 0 91250
result:
ok 4 number(s): "0 91251 0 91250"
Test #54:
score: 0
Accepted
time: 18ms
memory: 20764kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 4772 86479 91250
result:
ok 4 number(s): "1 4772 86479 91250"
Test #55:
score: 0
Accepted
time: 16ms
memory: 23208kb
input:
lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...
output:
48590 45626 0 91250
result:
ok 4 number(s): "48590 45626 0 91250"
Test #56:
score: 0
Accepted
time: 17ms
memory: 21760kb
input:
ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...
output:
22317 19352 36850 75552
result:
ok 4 number(s): "22317 19352 36850 75552"
Test #57:
score: 0
Accepted
time: 0ms
memory: 3484kb
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: 3428kb
input:
ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab abbbbaabaa
output:
1 7 43 99
result:
ok 4 number(s): "1 7 43 99"