QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90853#5256. InsertionschenshiAC ✓21ms23544kbC++2.4kb2023-03-25 21:00:222023-03-25 21:00:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-25 21:00:25]
  • 评测
  • 测评结果:AC
  • 用时:21ms
  • 内存:23544kb
  • [2023-03-25 21:00:22]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int o=1e5+10;
int n,m,lenp,nxtt[o],nxtp[o],nxtpr[o],len[o],lenr[o],v[o],h[o],cnt,dfn[o],ed[o],b[o],ans[o],ans1,ans2,ans3,ans4;
char s[o],t[o],p[o];vector<int> chg[o],ask[o];
inline int lowbit(int x){return x&-x;}
inline void modify(int pos,int val){for(;pos<=lenp+1;pos+=lowbit(pos)) b[pos]+=val;}
inline int query(int pos){int res=0;for(;pos;pos-=lowbit(pos)) res+=b[pos];return res;}
struct Edge{int v,p;}e[o];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
void Dfs(int nw){
	dfn[nw]=++cnt;
	for(int i=h[nw];i;i=e[i].p) Dfs(e[i].v);
	ed[nw]=cnt;
}
void dfs(int nw){
	for(int i=chg[nw].size(),t;i--;) t=chg[nw][i],modify(dfn[t],1),modify(ed[t]+1,-1);
	for(int i=ask[nw].size(),t;i--;) t=ask[nw][i],ans[t]+=query(dfn[lenp-lenr[t+1]+1]);
	for(int i=h[nw];i;i=e[i].p) dfs(e[i].v);
	for(int i=chg[nw].size(),t;i--;) t=chg[nw][i],modify(dfn[t],-1),modify(ed[t]+1,1);
}
inline void slv(){
	reverse(s+1,s+n+1);reverse(t+1,t+m+1);reverse(p+1,p+lenp+1);reverse(ans,ans+n+1);
	for(int i=1,j=nxtp[0]=-1;i<=lenp;nxtp[i++]=++j) for(;j+1&&p[j+1]-p[i];j=nxtp[j]);
	for(int i=1,j=nxtt[0]=-1;i<=m;nxtt[i++]=++j) for(;j+1&&t[j+1]-t[i];j=nxtt[j]);
	for(int i=1,j=0;i<=lenp;++i){
		for(;j+1&&t[j+1]-p[i];j=nxtt[j]);
		++j;
		if(i==lenp) for(;j;j=nxtt[j]) if(j<lenp&&j<m) ++v[lenp-j];
	}
	for(int i=1;i<=lenp;++i) v[i]+=v[nxtp[i]];
	for(int i=1,j=0,c=0;i<=n;++i){
		for(;j+1&&p[j+1]-s[i];j=nxtp[j]);
		c+=(lenp==++j);ans[i]+=c+v[len[i]=j];
	}
}
int main(){
	scanf("%s%s%s",s+1,t+1,p+1);n=strlen(s+1);m=strlen(t+1);lenp=strlen(p+1);
	slv();
	for(int i=0;i<=lenp;++i) nxtpr[lenp-i+1]=lenp-nxtp[i]+1,v[i]=0;
	for(int i=0;i<=n;++i) lenr[n-i+1]=len[i];
	slv();
	if(lenp<=m){
		for(int i=1,j=0;i<=m;++i){
			for(;j+1&&p[j+1]-t[i];j=nxtp[j]);
			ans1+=(lenp==++j);
		}
		for(int i=0;i<=n;++i) ans[i]+=ans1;
	}
	else{
		for(int i=1,j=0;i<=lenp;++i){
			for(;j+1&&t[j+1]-p[i];j=nxtt[j]);
			if(m==++j) chg[i-m].push_back(i+1);
		}
		for(int i=1;i<=lenp;++i) ad(nxtpr[i],i);
		cnt=0;Dfs(lenp+1);
		for(int i=0;i<=n;++i) ask[len[i]].push_back(i);
		cnt=0;
		for(int i=0;i<=lenp;++i) h[i]=0;
		for(int i=1;i<=lenp;++i) ad(nxtp[i],i);
		dfs(0);
	}
	for(int i=0;i<=n;++i) ans1=max(ans1,ans[i]);
	for(int i=0;i<=n;++i) if(ans[i]==ans1) ++ans2,ans4=i;
	for(int i=n;i+1;--i) if(ans[i]==ans1) ans3=i;
	printf("%d %d %d %d",ans1,ans2,ans3,ans4);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 12264kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

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

Test #2:

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

input:

z
zzkkzzkk
z

output:

5 2 0 1

result:

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

Test #3:

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

input:

wgwwggggw
g
gggg

output:

2 5 4 8

result:

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

Test #4:

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

input:

q
uuquu
u

output:

4 2 0 1

result:

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

Test #5:

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

input:

gpgggpppg
pg
gpgg

output:

2 1 4 4

result:

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

Test #6:

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

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: 9220kb

input:

aacaacacaa
ca
caca

output:

2 5 2 9

result:

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

Test #8:

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

input:

k
kekekkekk
k

output:

7 2 0 1

result:

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

Test #9:

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

input:

ghhhhg
g
ghhg

output:

2 1 3 3

result:

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

Test #10:

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

input:

b
xbb
b

output:

3 2 0 1

result:

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

Test #11:

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

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: 10052kb

input:

imiimmmm
miimi
i

output:

6 9 0 8

result:

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

Test #13:

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

input:

gzzzzzzzzz
zgzzzg
gzgggzzz

output:

0 11 0 10

result:

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

Test #14:

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

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: 11256kb

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: 12196kb

input:

f
ffffwff
wffw

output:

0 2 0 1

result:

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

Test #17:

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

input:

plpll
llplll
pppppppl

output:

0 6 0 5

result:

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

Test #18:

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

input:

yypppypyy
ppyyypppy
ypyppypp

output:

0 10 0 9

result:

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

Test #19:

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

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: 11640kb

input:

ccc
cpppp
cc

output:

3 1 3 3

result:

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

Test #21:

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

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

631 1000 0 999

result:

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

Test #22:

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

input:

annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...

output:

0 1000 0 999

result:

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

Test #23:

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

input:

atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...

output:

0 1000 0 999

result:

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

Test #24:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 413 587 999

result:

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

Test #25:

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

input:

rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...

output:

315 2 1 998

result:

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

Test #26:

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

input:

huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...

output:

260 1 113 113

result:

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

Test #27:

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

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

748 907 0 906

result:

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

Test #28:

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

input:

kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...

output:

0 907 0 906

result:

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

Test #29:

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

input:

illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...

output:

0 907 0 906

result:

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

Test #30:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

1 702 0 701

result:

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

Test #31:

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

input:

mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...

output:

374 454 0 906

result:

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

Test #32:

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

input:

kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...

output:

291 370 50 788

result:

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

Test #33:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

937 966 0 965

result:

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

Test #34:

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

input:

apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...

output:

35 64 600 663

result:

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

Test #35:

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

input:

msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...

output:

0 966 0 965

result:

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

Test #36:

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

input:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

1 768 0 767

result:

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

Test #37:

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

input:

jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...

output:

468 483 0 964

result:

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

Test #38:

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

input:

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...

output:

429 443 80 964

result:

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

Test #39:

score: 0
Accepted
time: 21ms
memory: 23544kb

input:

tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

44459 99774 0 99773

result:

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

Test #40:

score: 0
Accepted
time: 13ms
memory: 20920kb

input:

annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...

output:

0 99774 0 99773

result:

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

Test #41:

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

input:

eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...

output:

0 99774 0 99773

result:

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

Test #42:

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

input:

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1 61041 38733 99773

result:

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

Test #43:

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

input:

zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...

output:

22229 2 1 99772

result:

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

Test #44:

score: 0
Accepted
time: 19ms
memory: 19556kb

input:

babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...

output:

22229 2 1 99772

result:

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

Test #45:

score: 0
Accepted
time: 14ms
memory: 21716kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

85548 90750 0 90749

result:

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

Test #46:

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

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...

output:

0 90750 0 90749

result:

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

Test #47:

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

input:

llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...

output:

0 90750 0 90749

result:

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

Test #48:

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

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1 71220 19530 90749

result:

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

Test #49:

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

input:

qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...

output:

42774 45375 0 90748

result:

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

Test #50:

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

input:

xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...

output:

40492 43093 2508 88692

result:

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

Test #51:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

97181 91251 0 91250

result:

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

Test #52:

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

input:

vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

6028 98 22809 22906

result:

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

Test #53:

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

input:

qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...

output:

0 91251 0 91250

result:

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

Test #54:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 4772 86479 91250

result:

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

Test #55:

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

input:

lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...

output:

48590 45626 0 91250

result:

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

Test #56:

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

input:

ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...

output:

22317 19352 36850 75552

result:

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

Test #57:

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

input:

abbababa
babbba
bbab

output:

2 6 1 7

result:

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

Test #58:

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

input:

ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba
aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab
abbbbaabaa

output:

1 7 43 99

result:

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